#include <bits/stdc++.h>
using namespace std;
/*
se eu tenho um cara da esquerda sempre vale pegar primeiro cara que der da direita
se eu tenho um destino na direita sempre vale pegar o maior cara da esquerda q chega la
nenhuma subtituição nos intervalos muda nada pq
A=B e C=D:
esquece esquerda e direita
posso ir pro maior ou pro menor, pra toda decisão de ir pro menor o maior ainda é opção, ent sempre vale a pena enqunato puder ir maior, ir maior
busca binária com sparse
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 2e5+10, MAXQ = 1e5+10, BIG = 1e9+8, MAXB=20;
int n, h[MAXN];
int r[MAXN], l[MAXN];
int op[MAXN][MAXB], sb[MAXN][MAXB]; // optimal e suboptimal: op[i][j] = onde paro fazendo 2^j operações otimas partindo do elemento i
bool thing = 0;
void init(int N, vector<int> H){
n = N;
thing = 1;
for (int i=0;i<n;i++){
h[i] = H[i], l[i+1]=r[i+1]=i+1;
if (h[i]!=i+1) thing=0;
}
if (thing) return;
stack<int> ps;
for (int i=0;i<n;i++){
int x = h[i];
while (!ps.empty() && ps.top()<x){
r[ps.top()]=x;
ps.pop();
}
ps.push(x);
}
while (!ps.empty()) ps.pop();
for (int i=n-1;i>=0;i--){
int x = h[i];
while (!ps.empty() && ps.top()<x){
l[ps.top()]=x;
ps.pop();
}
ps.push(x);
}
for (int i=1;i<=n;i++){
op[i][0] = max(l[i], r[i]);
if (min(l[i], r[i]) == i) sb[i][0]=op[i][0];
else sb[i][0] = min(l[i], r[i]);
}
for (int j=1;j<MAXB;j++){
for (int i=1;i<=n;i++){
op[i][j] = op[op[i][j-1]][j-1], sb[i][j] = sb[sb[i][j-1]][j-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D){ // A <= B < C <= D
if (thing){
return C-B;
}
// assume A=B and C=D
int x = h[A], ds = h[C];
int ans=0;
for (int i=19;i>=0;i--) if (op[x][i]!=x && (i==0 || op[x][i]!=op[x][i-1])){
if (op[x][i]<=ds) x = op[x][i],ans+=(1<<i);
}
for (int i=19;i>=0;i--) if (sb[x][i]!=x && (i==0 || sb[x][i]!=sb[x][i-1])){
if (sb[x][i]<=ds) x=sb[x][i], ans += (1<<i);
}
// cerr << "end " << x << ' ' << ans << '\n';
if (x!=ds) return -1;
return ans;
}
