#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int M = 200'010; int maxlog = 17; int inf = 1e9; int base = 1<<18; vector<pair<int, int>> T(2*base,{0,0}); vector<int> L(M), R(M); vector<vector<int>> jp(M,vector<int>(maxlog+1)), jpL(M,vector<int>(maxlog+1)), jpR(M,vector<int>(maxlog+1)); vector<int> h; void update(int x, int val) { x+=base; T[x] = {val,x-base}; x/=2; while(x > 0) { T[x] = max(T[x+x], T[x+x+1]); x/=2; } } pair<int,int> query(int a, int b) { if(a>b) return {0,0}; if(a==b) return T[a+base]; a+=base-1; b+=base+1; pair<int, int> res = {0, 0}; while(a/2!=b/2) { if(a%2==0) res = max(res, T[a+1]); if(b%2==1) res = max(res, T[b-1]); a/=2; b/=2; } return res; } int get_ans(int a, int b, int c, int d) { int Z = query(b+1,c-1).first; int Y = query(c,d).second; int X = b; for(int i=maxlog; i>=0; --i) { if(h[jpL[X][i]] < h[Y] && jpL[X][i] >= a) X = jpL[X][i]; } Y=c; for(int i=maxlog; i>=0; --i) { if(h[jpR[Y][i]] <= max(h[X],Z) && jpR[Y][i] <= d) { Y = jpR[Y][i]; } } if(jpR[Y][0] <= d) Y = jpR[Y][0]; if(max(Z, h[X]) >= h[Y]) return -1; int res = 0; for(int i=maxlog; i>=0; --i) { if(h[jp[X][i]] < h[Y]) { X = jp[X][i]; res += (1<<i); } } for(int i=maxlog; i>=0; --i) { if(h[jpR[X][i]] < h[Y]) { X = jpR[X][i]; res += (1<<i); } } return res+1; } int minimum_jumps(int a, int b, int c, int d) { auto ch = [&](int x) { if(x==-1) return inf; return x; }; int ans = inf; for(int i=c; i<=d; ++i) ans = min(ans, ch(get_ans(a,b,i,i))); if(ans==inf) return -1; return ans; } void init(int n, vector<int> H) { h = H; for(int i=0; i<n; ++i) update(i,H[i]); stack<int> stos; for(int i=0; i<n; ++i) { while(stos.size() && H[stos.top()] <= H[i]) stos.pop(); if(stos.size()) L[i] = stos.top(); else L[i] = i; stos.push(i); } while(stos.size()) stos.pop(); for(int i=n-1; i>=0; --i) { while(stos.size() && H[stos.top()] <= H[i]) stos.pop(); if(stos.size()) R[i] = stos.top(); else R[i] = i; stos.push(i); } for(int i=0; i<n; ++i) { jpL[i][0] = L[i]; jpR[i][0] = R[i]; jp[i][0] = L[i]; if(H[R[i]] >= H[L[i]]) jp[i][0] = R[i]; } for(int j=1; j<=maxlog; ++j) { for(int i=0; i<n; ++i) { jp[i][j] = jp[jp[i][j-1]][j-1]; jpL[i][j] = jpL[jpL[i][j-1]][j-1]; jpR[i][j] = jpR[jpR[i][j-1]][j-1]; } } }