#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
int maxn = 1e8 + 5;
int nnn = 1048590;
int inf = numeric_limits<int>::max()-1;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dxx[]={0,1,0,-1,1,1,-1,-1};
int dyy[]={1,0,-1,0,1,-1,1,-1};
const int N = 2e5 + 5;
int a[N], n, p[N];
int lft[N] , rght[N];
int par[N][20], L[N][20], R[N][20];
struct seg_tree{
struct typo{
int mx;
void setup(int _sum){
mx = _sum;
}
};
vector < typo > b;
int n;
void init(int l, int r, int node){
b[node].setup(a[l]);
return;
}
typo merge(typo a, typo b){
typo c;
c.mx = max(a.mx, b.mx);
return c;
}
void build(int l, int r, int node){
if(l == r){
init(l,r,node);
return;
}
int mid = (l + r)/2;
int n1 = 2*node;
int n2 = n1 + 1;
build(l, mid , n1);
build(mid+1, r, n2);
b[node] = merge(b[n1] , b[n2]);
return;
}
void build(int _n){
n = _n;
b.resize(4*n);
build(1,n,1);
}
typo get(int l, int r, int node, int x, int y){
if(y < l || x > r) return {0};
if(x <= l && y >= r){
return b[node];
}
int mid = (l + r)/2;
int n1 = 2*node;
int n2 = n1 + 1;
return merge(get(l , mid , n1 , x , y) , get(mid + 1, r , n2 , x , y));
}
int get(int l, int r){
return get(1,n,1,l,r).mx;
}
}T;
void init(int _n, std::vector<int> H) {
n = _n;
for(int i = 1; i <= n; i++){
a[i] = H[i - 1];
p[a[i]] = i;
}
a[0] = a[n + 1] = n + 1;
stack < int > st;
st.push(0);
for(int i = 1; i <= n; i++){
while(st.size() && a[st.top()] < a[i]) st.pop();
lft[i] = st.top();
st.push(i);
}
while(st.size()) st.pop();
st.push(n + 1);
for(int i = n; i >= 1; i--){
while(st.size() && a[st.top()] < a[i]) st.pop();
rght[i] = st.top();
st.push(i);
}
for(int i = 0; i < 20; i++){
par[0][i] = L[0][i] = R[0][i] = 0;
par[n+1][i] = L[n+1][i] = R[n+1][i] = n+1;
}
for(int i = 1; i <= n; i++){
if(a[lft[i]] > a[rght[i]]) par[i][0] = lft[i];
else par[i][0] = rght[i];
L[i][0] = lft[i];
R[i][0] = rght[i];
}
for(int j = 1; j < 20; j++){
for(int i = 1; i <= n; i++){
par[i][j] = par[par[i][j - 1]][j - 1];
L[i][j] = L[L[i][j-1]][j-1];
R[i][j] = R[R[i][j-1]][j-1];
}
}
T.build(n);
return;
}
int apply(int x, int C, int D){
int res = 0;
for(int i = 19; i >= 0; i--){
if(R[x][i] < C) x = R[x][i], res += (1 << i);
}
if(rght[x] <= D) res++;
else res = 1e9;
return res;
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
int e = T.get(C,D);
if(a[B] > e) return -1;
int x = B;
for(int i = 19; i >= 0; i--){
if(A <= L[x][i] && a[L[x][i]] < e) x = L[x][i];
}
int prob = T.get(x, C-1);
if(prob > e) return -1;
int ans = 0;
for(int i = 19; i >= 0; i--){
if(a[par[x][i]] <= prob){
ans += (1 << i);
x = par[x][i];
}
}
int k = apply(x, C, D);
if(lft[x]) k = min(k, 1 + apply(lft[x], C,D));
if(k > n) return -1;
return ans + k;
}
