#include "jumps.h"
#include<bits/stdc++.h>
#ifdef VANWIJ
#define DBG 1
#else
#define DBG 0
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}
const int N = 2e5+5;
const int LN = 18;
int n;
int a[N];
V<int> adj[N];
int pl[N][LN], pr[N][LN];
int hi[N][LN], lo[N][LN];
void init(int _n, V<int> _a){
n = _n;
rep(i,0,n) a[i] = _a[i];
// leftward edges
V<int> stak;
rep(i,0,n){
while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
int j = stak.empty() ? i : stak.back();
pl[i][0] = j;
if(i!=j) adj[i].push_back(j);
stak.push_back(i);
}
// rightward edges
stak.clear();
for(int i=n-1; i>=0; i--){
while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
int j = stak.empty() ? i : stak.back();
pr[i][0] = j;
if(i!=j) adj[i].push_back(j);
stak.push_back(i);
}
rep(i,0,n){
if(adj[i].empty()) adj[i].push_back(i);
if(adj[i].size()==1) adj[i].push_back(adj[i][0]);
if(!(a[adj[i][0]] <= a[adj[i][1]])){
swap(adj[i][0], adj[i][1]);
}
lo[i][0] = adj[i][0];
hi[i][0] = adj[i][1];
}
rep(lg,1,LN) rep(i,0,n){
pl[i][lg] = pl[pl[i][lg-1]][lg-1];
pr[i][lg] = pr[pr[i][lg-1]][lg-1];
hi[i][lg] = hi[hi[i][lg-1]][lg-1];
lo[i][lg] = lo[lo[i][lg-1]][lg-1];
}
}
int minimum_jumps(int A,int B,int C,int D){
// touching
if(B==C-1){
if(pr[B][0] <= D) return 1;
return -1;
}
// maximum in [B+1..C-1]
int m = B+1;
for(int b=LN-1; b>=0; b--){
int x = pr[m][b];
if(x<C) m = x;
}
if(a[B] > a[m]){
if(pr[B][0] <= D) return 1;
return -1;
}
// // maximum in [C..D]
// int t = C;
// for(int b=LN-1; b>=0; b--){
// int x = pr[t][b];
// if(x<=D) t = x;
// }
// maximum in [A..B] not over a[m]
int s = B;
for(int b=LN-1; b>=0; b--){
int x = pl[s][b];
if(A<=x && a[x]<a[m]) s = x;
}
// // impossible
// if(!(a[s] < a[t])) return -1;
// if(!(a[m] < a[t])) return -1;
// // if jump over m
// for(int x : adj[s]){
// if(C<=x && x<=D) return 1;
// }
// WLOG a[s] < a[m]
// jump over m
int ans = 0;
// there is better in interval
if(A <= pl[s][0]){
// if jump over
int x = pr[pl[s][0]][0];
if(C<=x && x<=D) return 1;
// no need to go left since it will land at over a[t]
}
else{
// hi edges, not passing a[m]
for(int b=LN-1; b>=0; b--){
int x = hi[s][b];
if(a[x]<=a[m]){
s = x;
ans += 1<<b;
}
}
// stopped at m
if(s==m){
if(C<=pr[s][0] && pr[s][0]<=D) return ans+1;
return -1;
}
// if jump over
{
int x = pr[pl[s][0]][0];
if(C<=x && x<=D) return ans+2;
}
}
// rightward edges
// leftward is not possible, since it coulve been skipped
for(int b=LN-1; b>=0; b--){
int x = pr[s][b];
if(x < C){
s = x;
ans += 1<<b;
}
}
s = pr[s][0];
ans++;
if(C<=s && s<=D) return ans;
return -1;
}
