#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int maxn = (int)2e5+10;
const int maxlg = 24;
const int INF = (int)1e9;
int n, pr[maxn], nx[maxn];
int high[maxlg][maxn], movR[maxlg][maxn];
void calc(int jmp[][maxn]){
for(int i = 1; i < maxlg; i++)
for(int j = 0; j < n; j++)
if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}
void init(int N, vector<int> a) {
n = N;
stack<pair<int,int>> S;
memset(pr,-1,sizeof(pr));
memset(nx,-1,sizeof(nx));
memset(high,-1,sizeof(high));
memset(movR,-1,sizeof(movR));
for(int i = 0; i < n; i++){
while(!S.empty() and S.top().fi<a[i]) S.pop();
if(!S.empty()) pr[i] = S.top().se;
S.push({a[i],i});
}
while(!S.empty()) S.pop();
for(int i = n-1; i>=0; i--){
while(!S.empty() and S.top().fi<a[i]) S.pop();
if(!S.empty()) nx[i] = S.top().se;
S.push({a[i],i});
}
while(!S.empty()) S.pop();
for(int i = 0; i < n; i++){
if(nx[i]!=-1) movR[0][i]=nx[i];
if(pr[i]!=-1 and nx[i]!=-1)
high[0][i] = (a[pr[i]]<a[nx[i]]?nx[i]:pr[i]);
}
calc(high), calc(movR);
}
int get_path(int *x, int y, int z, int jmp[][maxn], int range=maxn){
int tot = 0; range = min(range, y);
for(int i = 20; i >= 0; i--)
if(jmp[i][*x]!=-1 and jmp[i][*x]<range)
if(nx[jmp[i][*x]]!=-1 and nx[jmp[i][*x]]<=z)
*x = jmp[i][*x], tot+=(1<<i);
return tot;
}
int minimum_jumps(int A, int B, int C, int D) {
int x = A;
for(int i = B; i >= A; i--){
if(nx[i]==-1 or nx[i]>D) continue;
x=i; break;
}
int num1 = get_path(&x,C,D,high);
int num2 = get_path(&x,C,D,movR);
return ((nx[x]>=C and nx[x]<=D)?num1+num2+1:-1);
}
