#include "jumps.h"
#include<iostream>
#include<algorithm>
#include <vector>
#include <stack>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
const int inf = 1e9+10;
const int maxn = 2e5+10;
int n, h[maxn], nx[maxn][23], nxl[maxn][23], nxr[maxn][23];
pair<int,int> tr[4*maxn];
void att(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
tr[no] = mp(val,pos);
return;
}
int mid = (l+r)>>1;
att(2*no,l,mid,pos,val);
att(2*no+1,mid+1,r,pos,val);
tr[no] = max(tr[2*no],tr[2*no+1]);
}
pair<int,int> qrmx(int no, int l, int r, int L, int R) {
if(l > R || r < L) return mp(-inf,0);
if(l >= L && r <= R) {
return tr[no];
}
int mid = (l+r)>>1;
return max(qrmx(2*no,l,mid,L,R),qrmx(2*no+1,mid+1,r,L,R));
}
void init(int N, std::vector<int> H) {
n = N;
for(int i = 0; i < n; i++) {
h[i] = H[i];
att(1,0,n-1,i,h[i]);
}
stack<pair<int,int>> stk;
for(int i = 0; i < n; i++) {
while(stk.size() && stk.top().fr < h[i]) stk.pop();
if(stk.size()) nxl[i][0] = stk.top().sc;
else nxl[i][0] = n;
stk.push(mp(h[i],i));
}
while(stk.size()) stk.pop();
for(int i = n-1; i >= 0; i--) {
while(stk.size() && stk.top().fr < h[i]) stk.pop();
if(stk.size()) nxr[i][0] = stk.top().sc;
else nxr[i][0] = n;
stk.push(mp(h[i],i));
}
for(int i = 0; i < n; i++) {
if(nxr[i][0] == n) nx[i][0] = nxl[i][0];
else if(nxl[i][0] == n) nx[i][0] = nxr[i][0];
else if(h[nxl[i][0]] > h[nxr[i][0]]) nx[i][0] = nxl[i][0];
else nx[i][0] = nxr[i][0];
// cout << i << " - " << nx[i][0] << endl;
}
nx[n][0] = n;
nxl[n][0] = n;
nxr[n][0] = n;
for(int j = 1; j <= 20; j++) {
for(int i = 0; i <= n; i++) {
nx[i][j] = nx[nx[i][j-1]][j-1];
nxl[i][j] = nxl[nxl[i][j-1]][j-1];
nxr[i][j] = nxr[nxr[i][j-1]][j-1];
// cout << i << " " << j << " " << nx[i][j] << endl;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0;
int f = qrmx(1,0,n-1,C,D).sc;
if(nxl[f][0] < n) A = max(A,nxl[f][0]+1);
if(A > B) return -1;
int v = qrmx(1,0,n-1,A,B).sc;
// cout << f << " " << v << " " << nx[v][20] << endl;
for(int j = 20; j >= 0; j--) {
int nxv = nx[v][j];
if(nxr[nxv][0] < C) {
ans+= (1<<j);
v = nxv;
}
}
int v1 = v;
int ans1 = ans;
int v2 = nx[v][0];
int ans2 = ans+1;
// cout << v1 << " " << v2 << " " << ans1<< endl;
ans = inf;
for(int j = 20; j >= 0; j--) {
int nxv = nxr[v1][j];
// cout << j << " " << v1 << " " << nxv << endl;
if(nxv < C) {
v1 = nxv;
ans1+= (1<<j);
}
}
// cout << v1 << " " << v2 << " " << ans1<< endl;
if(C <= nxr[v1][0] && nxr[v1][0] <= D) ans = min(ans,ans1+1);
for(int j = 1; j >= 0; j--) {
int nxv = nxr[v2][j];
if(nxv < C) {
v2 = nxv;
ans2+= (1<<j);
}
}
// cout << v1 << " " << v2 << " " << ans2<< endl;
if(C <= nxr[v2][0] && nxr[v2][0] <= D) ans = min(ans,ans2+1);
if(ans == inf) return -1;
return ans;
}
