#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define inf (ll)(1e15)
#define dbg(x) cerr <<#x << ' ' << x <<endl;
using namespace std;
ll n;
vector<ll> h;
vector<pair<ll,ll>> mn;
vector<ll> ind;
vector<ll> limn;
vector<vector<ll>> nqqz;
vector<vector<ll>> nqqz2;
ll maxn=2e5;
vector<ll> tree(4*maxn+3);
ll rnd(ll l, ll r)
{
return rand()%(r-l+1)+l;
}
void update(ll node, ll l, ll r, ll pos, ll val)
{
if(pos < l || pos > r)return;
if(l==r)
{
tree[node]=val;
return;
}
ll mid=(l+r)/2;
update(node*2+1,l,mid,pos,val);
update(node*2+2,mid+1,r,pos,val);
tree[node]=max(tree[node*2+1],tree[node*2+2]);
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
if(max(l,x) > min(r,y))return 0;
if(x<=l && r<=y)return tree[node];
ll mid=(l+r)/2;
return max(query(node*2+1,l,mid,x,y),query(node*2+2,mid+1,r,x,y));
}
void init(int N, std::vector<int> H)
{
h.clear();
mn.clear();
ind.clear();
limn.clear();
nqqz.clear();
nqqz2.clear();
tree.clear();
n=N;
for (int i=0;i<n;i++) h.push_back(H[i]);
mn.resize(n+1);
stack<ll> s;
for (int i=0;i<n;i++)
{
while(s.size() && (s.top() < h[i]))
{
s.pop();
}
if(s.size())
{
mn[h[i]].first=s.top();
}
s.push(h[i]);
}
while(s.size())s.pop();
for (int i=n-1;i>=0;i--)
{
while(s.size() && (s.top() < h[i]))
{
s.pop();
}
if(s.size())
{
mn[h[i]].second=s.top();
}
s.push(h[i]);
}
ind.resize(n+1);
for (int i=0;i<n;i++)
{
ind[h[i]]=i;
update(0,0,n-1,i,h[i]);
}
limn.resize(n+1);
for (int i=n-1;i>=0;i--)
{
if(mn[h[i]].second!=0)
{
limn[h[i]]=1+limn[mn[h[i]].second];
}
}
nqqz.assign(n+1,vector<ll>(20,inf));
nqqz2.assign(n+1,vector<ll>(20,inf));
for (int i=n;i>=1;i--)
{
for (int j=0;j<20;j++)
{
if(j==0)
{
if(max(mn[i].first,mn[i].second)!=0)
{
nqqz[i][j]=max(mn[i].first,mn[i].second);
}
}
else
{
if(max(mn[i].first,mn[i].second)!=0)
{
ll x=nqqz[i][j-1];
if(x!=inf)
{
nqqz[i][j]=nqqz[x][j-1];
}
}
}
}
}
// tnqiza 2:
for (int i=n;i>=1;i--)
{
for (int j=0;j<20;j++)
{
if(j==0)
{
if(mn[i].second!=0)
{
nqqz2[i][j]=mn[i].second;
}
}
else
{
if(mn[i].second!=0)
{
ll x=nqqz2[i][j-1];
if(x!=inf)
{
nqqz2[i][j]=nqqz2[x][j-1];
}
}
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
ll kbir=query(0,0,n-1,C,D);
if(mn[kbir].first!=0 && ind[mn[kbir].first] >= B) return -1;
ll awal;
if(mn[h[C]].first==0 || ind[mn[h[C]].first] < B) awal=h[C];
else
{
awal=h[B];
for (int j=19;j>=0;j--)
{
if(nqqz2[awal][j] != inf && ind[nqqz2[awal][j]]<C)
{
awal=nqqz2[awal][j];
}
}
awal=nqqz2[awal][0];
}
// dbg(awal);
ll indd=A;
if(mn[kbir].first!=0)
{
indd=max(ind[mn[kbir].first]+1,(ll)A);
}
ll cur=query(0,0,n-1,indd,B);
if(cur > awal) return 1;
ll ans=0;
for (int j=19;j>=0;j--)
{
if(nqqz[cur][j]!=inf && nqqz[cur][j]<awal)
{
cur=nqqz[cur][j];
ans+=1LL<<j;
}
}
if(mn[cur].second==awal) return ans+1;
if(mn[cur].first < kbir) return ans+2;
return ans + limn[cur]-limn[awal];
}
// int minimum_jumps2(int A, int B, int C, int D) {
// vector<ll> dp(n+1,inf);
// for (int i=n;i>=1;i--)
// {
// if(C<=ind[i] && ind[i]<=D)
// {
// dp[i]=0;
// // dbg(i);
// }
// else
// {
// if(mn[i].first!=0) dp[i]=min(dp[i],1+dp[mn[i].first]);
// if(mn[i].second!=0) dp[i]=min(dp[i],1+dp[mn[i].second]);
// // cout << "here " << i << ' ' << dp[i] << endl;
// }
// }
// ll ans=inf;
// for (int i=A;i<=B;i++)
// {
// ans=min(ans,dp[h[i]]);
// }
// if(ans==inf)return -1;
// else return ans;
// }
// void stresstest()
// {
// for (int j=0;j<500;j++)
// {ll n=rnd(2,10);
// vector<int> v(n);
// for (int i=1;i<=n;i++) v[i-1]=i;
// mt19937 rng(j);
// shuffle(v.begin(),v.end(),rng);
// init(n,v);
// vector<ll> indices;
// for (int i=0;i<4;i++)
// {
// ll x=rnd(0,n-1);
// indices.push_back(x);
// }
// sort(indices.begin(),indices.end());
// if(indices[1]==indices[2])continue;
// cout << n << endl;
// for (auto &&e : v)
// {
// cout << e << ' ';
// }
// cout << endl;
// cout << "indices ";
// for (auto &&e : indices)
// {
// cout << e << ' ';
// }
// cout << endl;
// ll ans1=minimum_jumps2(indices[0],indices[1],indices[2],indices[3]);
// ll ans2=minimum_jumps(indices[0],indices[1],indices[2],indices[3]);
// cout << "answers " << ans1 << ' ' << ans2 << endl;
// if(ans1!=ans2)
// {
// break;
// }
// }
// }
// int main()
// {
// stresstest();
// }
