//chockolateman
#include<bits/stdc++.h>
using namespace std;
int n,a[200005],pos[200005],best[200005][20],nxt[200005][20],st[800005];
void build(int v = 1,int start = 1,int end = n)
{
if(start==end)
{
st[v] = a[start];
return;
}
int mid = (start + end)/2;
build(2*v,start,mid);
build(2*v+1,mid+1,end);
st[v] = max(st[2*v],st[2*v+1]);
}
int query(int l,int r,int v = 1,int start = 1,int end = n)
{
if(start==l && end==r)
return st[v];
int mid = (start + end)/2;
if(r <= mid)
return query(l,r,2*v,start,mid);
else if(l > mid)
return query(l,r,2*v+1,mid+1,end);
else
return max(query(l,mid,2*v,start,mid),query(mid+1,r,2*v+1,mid+1,end));
}
void init(int N, std::vector<int> H) {
n = N;
for(int i = 1 ; i <= N ; i++)
{
a[i] = H[i-1];
pos[a[i]] = i;
}
build();
stack<pair<int,int>> ord;
for(int i = N ; i >= 1 ; i--)
{
while(!ord.empty() && ord.top().first < a[i])
ord.pop();
if(ord.empty())
nxt[i][0] = i;
else
nxt[i][0] = ord.top().second;
for(int L = 1 ; L <= 18 ; L++)
nxt[i][L] = nxt[nxt[i][L-1]][L-1];
ord.push({a[i],i});
}
while(!ord.empty())
ord.pop();
for(int i = 1 ; i <= N ; i++)
{
while(!ord.empty() && ord.top().first < a[i])
ord.pop();
int prv;
if(ord.empty())
prv = i;
else
prv = ord.top().second;
if(a[nxt[i][0]] > a[prv])
best[i][0] = nxt[i][0];
else
best[i][0] = prv;
ord.push({a[i],i});
}
for(int L = 1 ; L <= 18 ; L++)
for(int i = 1 ; i <= N ; i++)
best[i][L] = best[best[i][L-1]][L-1];
}
int solve(int x,int C,int D,int maxim)
{
int ret = 0;
for(int L = 18 ; L >= 0 ; L--)
while(nxt[x][L] < C && best[x][L] < C && a[best[x][L]] < maxim)
{
x = best[x][L];
ret += (1<<L);
}
for(int L = 18 ; L >= 0 ; L--)
if(nxt[x][L] < C)
{
x = nxt[x][L];
ret += (1<<L);
}
ret++;
return ret;
}
int minimum_jumps(int A, int B, int C, int D) {
A++;
B++;
C++;
D++;
if(pos[query(B,D)] < C)
return -1;
int maxim = query(C,D);
int l = A;
int r = B;
while(l < r)
{
int mid = (l + r)/2;
int cur = query(mid,r);
if(cur < maxim)
r = mid;
else
l = mid + 1;
}
int x = pos[query(l,B)];
int ans = 1e9;
for(int i = A ; i <= B ; i++) //try A = B
{
// for(int j = C ; j <= D ; j++)
if(pos[query(i,D)] >= C)
ans = min(ans,solve(i,C,D,maxim));
}
return ans;
return solve(x,C,D,maxim);
}
