#include "jumps.h" #include<bits/stdc++.h> using namespace std; const int N = 2e5+5; const int lg = 18; int st1[N][lg],st2[N][lg],dp[N][lg]; void init(int N, vector<int>H){ int n = N; H.push_back(-1); vector<int>h; swap(h,H); for(int i = 0; i <= n; i++) st1[i][0] = st2[i][0] = dp[i][0] = n; stack<int>s; for(int i = n-1; i >= 0; i--){ while(s.size() && h[s.top()] <= h[i]) s.pop(); if(s.size()) st2[i][0] = s.top(); s.push(i); } while(s.size()) s.pop(); for(int i = 0; i <= n-1; i++){ while(s.size() && h[s.top()] <= h[i]) s.pop(); if(s.size()) st1[i][0] = s.top(); s.push(i); } for(int i = 0; i <= n-1; i++){ if(h[st1[i][0]] > h[st2[i][0]]) dp[i][0] = st1[i][0]; else dp[i][0] = st2[i][0]; } for(int j = 1; j < lg; j++){ for(int i = 0; i <= n; i++){ st1[i][j] = st1[st1[i][j-1]][j-1]; st2[i][j] = st2[st2[i][j-1]][j-1]; dp[i][j] = dp[dp[i][j-1]][j-1]; } } } int minimum_jumps(int A, int B, int C, int D){ int u = B; for(int i = lg-1; i >= 0; i--){ if(st1[u][i] >= A && st2[st1[u][i]][0] <= D) u = st1[u][i]; } if(C <= st2[u][0] && st2[u][0] <= D) return 1; int ans = 0; for(int i = lg-1; i >= 0; i--){ if(dp[u][i] < C){ ans += (1 << i); u = dp[u][i]; } } if(st2[dp[u][0]][0] <= D) return ans+2; for(int i = lg-1; i >= 0; i--){ if(st2[u][i] < C){ u = st2[u][i]; ans += (1 << i); } } if(st2[u][0] < C || st2[u][0] > D) return -1; return ans+1; }