//chockolateman
#include<bits/stdc++.h>
using namespace std;
int n,l[200005],r[200005],a[200005],up_max[200005][20],up_min[200005][20],max_st[200005];
set<int> st[200005]; //merge sort tree
void build(int v = 1,int start = 1,int end = n)
{
if(start==end)
{
st[v].insert(a[start]);
max_st[v] = a[start];
return;
}
int mid = (start + end)/2;
build(2*v,start,mid);
build(2*v+1,mid+1,end);
for(auto x : st[2*v])
st[v].insert(x);
for(auto x : st[2*v+1])
st[v].insert(x);
max_st[v] = max(max_st[2*v],max_st[2*v+1]);
}
int query(int left,int right,int val,int v = 1,int start = 1,int end = n)
{
if(start==left && end==right)
{
if(*st[v].begin() > val)
return 0;
if(*st[v].rbegin() <= val)
return *st[v].rbegin();
auto it = st[v].upper_bound(val);
it--;
return *it;
}
int mid = (start + end)/2;
if(right <= mid)
return query(left,right,val,2*v,start,mid);
else if(left > mid)
return query(left,right,val,2*v+1,mid+1,end);
else
return max(query(left,mid,val,2*v,start,mid),query(mid+1,right,val,2*v+1,mid+1,end));
}
int query_max(int left,int right,int v = 1,int start = 1,int end = n)
{
if(start==left && end==right)
return max_st[v];
int mid = (start + end)/2;
if(right <= mid)
return query_max(left,right,2*v,start,mid);
else if(left > mid)
return query_max(left,right,2*v+1,mid+1,end);
else
return max(query_max(left,mid,2*v,start,mid),query_max(mid+1,right,2*v+1,mid+1,end));
}
void init(int N, std::vector<int> H) {
for(int i = 1 ; i <= N ; i++)
a[i] = H[i-1];
n = N;
stack<int> order;
order.push(N+1);
for(int i = 1 ; i <= N ; i++)
{
while(H[i-1] > order.top())
order.pop();
l[a[i]] = order.top();
order.push(a[i]);
}
while(!order.empty())
order.pop();
order.push(N+1);
for(int i = N ; i >= 1 ; i--)
{
while(H[i-1] > order.top())
order.pop();
r[a[i]] = order.top();
order.push(a[i]);
}
for(int L = 18 ; L >= 0 ; L--)
up_max[N+1][L] = N+1;
for(int i = 1 ; i <= N ; i++)
up_max[i][0] = max(l[i],r[i]);
for(int L = 1 ; L <= 18 ; L++)
for(int i = 1 ; i <= N ; i++)
up_max[i][L] = up_max[up_max[i][L-1]][L-1];
for(int L = 18 ; L >= 0 ; L--)
up_min[N+1][L] = N+1;
for(int i = 1 ; i <= N ; i++)
up_min[i][0] = min(l[i],r[i]);
for(int L = 1 ; L <= 18 ; L++)
for(int i = 1 ; i <= N ; i++)
up_min[i][L] = up_min[up_min[i][L-1]][L-1];
build();
}
int ans(long long v,long long targ)
{
long long sums = (1ll<<18);
long long ret = 0;
for(int L = 18 ; L >= 0 ; L--)
{
while (up_max[v][L] <= targ)
{
v = up_max[v][L];
ret += sums;
}
sums /= 2;
}
sums = (1ll<<18);
for(int L = 18 ; L >= 0 ; L--)
{
while (up_min[v][L] <= targ)
{
v = up_min[v][L];
ret += sums;
}
sums /= 2;
}
if(v != targ)
ret = n+1;
return ret;
}
int minimum_jumps(int A, int B, int C, int D) {
A++;
B++;
C++;
D++;
int ret = 1e9;
for(int j = C ; j <= D ; j++)
{
int front_chose = 0;
int left = B;
if(a[left] > a[j])
continue;
for(int b = n ; b >= 1 ; b/=2)
while(left - b >= A && query_max(left-b,B) <= a[j])
left -= b;
front_chose = query_max(left,B);
for(int i = B ; i >= A ; i--)
if(a[i] <= a[j])
front_chose = max(front_chose,a[i]);
else
break;
if(front_chose==0)
continue;
ret = min(ret,ans(front_chose,a[j]));
}
if(ret > n)
ret = -1;
return ret;
}
