#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=201000; #define LOGN 25 int a[N],l[N],r[N],mn[N][LOGN],mx[N][LOGN]; bool check(int x,int y) { if (x==y) return true; per(i,0,LOGN) if (a[mn[x][i]]<a[y]) x=mn[x][i]; return mn[x][0]==y; } int dist(int x,int y) { if (x==y) return 0; int ans=0; per(i,0,LOGN) if (a[mn[x][i]]<a[y]) ans+=(1<<i),x=mn[x][i]; return ans+1; } void init(int n,VI h) { rep(i,0,n) a[i]=h[i]; stack<int> stk; rep(i,0,n) { while (SZ(stk)&&h[stk.top()]<h[i]) stk.pop(); if (SZ(stk)) l[i]=stk.top(); else l[i]=i; stk.push(i); } while (SZ(stk)) stk.pop(); per(i,0,n) { while (SZ(stk)&&h[stk.top()]<h[i]) stk.pop(); if (SZ(stk)) r[i]=stk.top(); else r[i]=i; stk.push(i); } rep(i,0,n) mn[i][0]=(h[l[i]]<h[r[i]]?l[i]:r[i]); rep(i,0,n) mx[i][0]=(h[l[i]]>h[r[i]]?l[i]:r[i]); rep(j,1,LOGN) rep(i,0,n) mn[i][j]=mn[mn[i][j-1]][j-1]; rep(j,1,LOGN) rep(i,0,n) mx[i][j]=mx[mx[i][j-1]][j-1]; } int calc(int a,int c) { if (!check(a,c)) return 1e9; int ans=0; per(i,0,LOGN) if (check(mx[a][i],c)) ans+=(1<<i),a=mx[a][i]; return ans+dist(a,c); } int minimum_jumps(int a,int b,int c,int d) { int ans=calc(a,c); if (ans==1e9) return -1; return ans; }