#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define maxs(a, b) (a = max(a, b))
const int MXN = 2e5+5;
const int LOG = 18;
int n, a[MXN], L[MXN], R[MXN];
int lft[LOG][MXN], rgt[LOG][MXN], nxt[LOG][MXN], mx[2][LOG][MXN];
int get_max(int l, int r) {
for(int i=LOG-1; i>=0; i--)
if(lft[i][r]>=l)
r = lft[i][r];
return a[r];
}
void init(int N, vector<int> H) {
n = N;
a[0] = a[n+1] = 1e9;
for(int i=1; i<=n; i++) {
a[i] = H[i-1];
for(L[i]=i-1; a[L[i]]<=a[i]; L[i]=L[L[i]]);
lft[0][i] = L[i];
for(int j=1; j<LOG; j++)
lft[j][i] = lft[j-1][lft[j-1][i]];
}
for(int i=0; i<LOG; i++) rgt[i][n+1] = n+1;
for(int i=n; i>=1; i--) {
for(R[i]=i+1; a[R[i]]<=a[i]; R[i]=R[R[i]]);
rgt[0][i] = R[i];
for(int j=1; j<LOG; j++)
rgt[j][i] = rgt[j-1][rgt[j-1][i]];
}
for(int i=0; i<LOG; i++) {
nxt[i][0] = 0;
nxt[i][n+1] = n+1;
mx[0][i][0] = 0;
mx[1][i][0] = 1e9;
mx[0][i][n+1] = n+1;
mx[1][i][n+1] = 1e9;
}
for(int i=1; i<=n; i++)
if(a[L[i]]>a[R[i]]) {
nxt[0][i] = L[i];
mx[0][0][i] = L[i];
mx[1][0][i] = a[L[i]];
}
else {
nxt[0][i] = R[i];
mx[0][0][i] = R[i];
mx[1][0][i] = a[R[i]];
}
for(int i=1; i<LOG; i++)
for(int j=1; j<=n; j++)
nxt[i][j] = nxt[i-1][nxt[i-1][j]],
mx[0][i][j] = max(mx[0][i-1][j], mx[0][i-1][nxt[i-1][j]]),
mx[1][i][j] = max(mx[1][i-1][j], mx[1][i-1][nxt[i-1][j]]);
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
int mx2 = get_max(C, D);
if(get_max(B, C-1)>mx2) return -1;
int v=B;
for(int i=LOG-1; i>=0; i--)
if(lft[i][v]>=A && a[lft[i][v]]<mx2)
v = lft[i][v];
// int ans = 1;
// for(int i=LOG-1; i>=0; i--)
// if(mx[0][i][v]<C && mx[1][i][v]<mx2)
// ans += 1<<i,
// v = nxt[i][v];
// for(int i=LOG-1; i>=0; i--)
// if(rgt[i][v]<C)
// ans += 1<<i,
// v = rgt[i][v];
int ans = 0;
while(R[v]<C && a[L[v]]<mx2) {
ans++;
if(a[L[v]]>a[R[v]]) v = L[v];
else v = R[v];
}
while(v<C) {
ans++;
v = R[v];
}
return ans;
}
