#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
#include "jumps.h"
struct segtree
{
int k=1;
int mn[550001],mx[550001];
int l[550001],r[550001];
void Build(vector<int> &niz, int n)
{
while (k<n) k*=2;
ff(i,0,k) l[i+k]=i,r[i+k]=i;
bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
ff(i,0,n) mn[i+k]=niz[i],mx[i+k]=niz[i];
bff(i,1,k) mn[i]=min(mn[2*i],mn[2*i+1]);
bff(i,1,k) mx[i]=max(mx[2*i],mx[2*i+1]);
}
int Min(int p, int ll, int rr)
{
if (ll>r[p] || rr<l[p]) return mod;
if (ll<=l[p] && rr>=r[p]) return mn[p];
return min(Min(2*p,ll,rr),Min(2*p+1,ll,rr));
}
int Max(int p, int ll, int rr)
{
if (ll>r[p] || rr<l[p]) return -mod;
if (ll<=l[p] && rr>=r[p]) return mx[p];
return max(Max(2*p,ll,rr),Max(2*p+1,ll,rr));
}
} ST;
int h[200005],gde[200005];
int levo[200005],desno[200005];
int opt[20][200005]; //jumping jacks
int grb[20][200005]; //naivno teranje udesno
int n;
void init(int N, vector<int> H)
{
n=N;
ff(i,0,n) h[i]=H[i],gde[h[i]]=i;
stack<int> mono;
ff(i,0,n)
{
while (!mono.empty() && h[mono.top()]<h[i]) mono.pop();
if (mono.empty()) levo[i]=-1; else levo[i]=mono.top();
mono.push(i);
}
while (!mono.empty()) mono.pop();
bff(i,0,n)
{
while (!mono.empty() && h[mono.top()]<h[i]) mono.pop();
if (mono.empty()) desno[i]=-1; else desno[i]=mono.top();
mono.push(i);
}
ff(i,0,n)
{
if (levo[i]==-1) opt[0][i]=desno[i];
else if (desno[i]==-1) opt[0][i]=levo[i];
else opt[0][i]=(h[levo[i]]>h[desno[i]]?levo[i]:desno[i]);
}
ff(k,1,20) ff(i,0,n)
{
if (opt[k-1][i]==-1) opt[k][i]=-1;
else opt[k][i]=opt[k-1][opt[k-1][i]];
}
ff(i,0,n) grb[0][i]=desno[i];
ff(k,1,20) ff(i,0,n)
{
if (grb[k-1][i]==-1) grb[k][i]=-1;
else grb[k][i]=grb[k-1][grb[k-1][i]];
}
ST.Build(H,n);
/*ff(i,0,n) cout<<levo[i]<<" "; cout<<endl;
ff(i,0,n) cout<<desno[i]<<" "; cout<<endl;
cout<<endl;*/
/*ff(k,0,20)
{
ff(i,0,n) cout<<opt[k][i]<<" ";
cout<<endl;
} cout<<endl;*/
/*ff(k,0,20)
{
ff(i,0,n) cout<<grb[k][i]<<" ";
cout<<endl;
} cout<<endl;*/
}
bool presisao(int ko, int C, int D, int plafon)
{
if (ko==-1) return true;
if (h[ko]>plafon) return true;
if (ko>=C) return true;
if (desno[ko]>=C) return true;
return false;
}
bool staje(int ko, int C, int D)
{
return C<=ko && ko<=D;
}
int putuj(int ko, int C, int D, int plafon)
{
int skokovi=0;
bff(k,0,20) if (!presisao(opt[k][ko],C,D,plafon)) ko=opt[k][ko],skokovi+=(1<<k);
if (staje(ko,C,D)) return skokovi;
if (staje(desno[ko],C,D)) return skokovi+1;
if (desno[ko]!=-1 && staje(desno[desno[ko]],C,D)) return skokovi+2;
if (levo[ko]!=-1 && staje(desno[levo[ko]],C,D)) return skokovi+2;
while (levo[ko]!=-1 && h[levo[ko]]<plafon) ko=levo[ko],skokovi++; ///ne bi trebalo da pogorsa slozenost...
bff(k,0,20) if (grb[k][ko]!=-1 && grb[k][ko]<C) ko=grb[k][ko],skokovi+=(1<<k);
if (!staje(ko,C,D)) ko=grb[0][ko],skokovi++;
if (staje(ko,C,D)) return skokovi;
return mod;
}
int minimum_jumps(int A, int B, int C, int D)
{
vector<int> putnici;
int plafon=ST.Max(1,C,D);
int bridge=ST.Max(1,B+1,C-1);
int l=A-1,r=B+1;
while (r-l>1)
{
int mid=(l+r)/2;
if (ST.Max(1,mid,B)<bridge) r=mid;
else l=mid;
}
if (l>=A) putnici.pb(l);
if (r<=B)
{
int sta=ST.Max(1,r,B);
l=r,r=B+1;
while (r-l>1)
{
int mid=(l+r)/2;
if (ST.Max(1,mid,B)==sta) l=mid;
else r=mid;
}
putnici.pb(l);
}
int ans=mod;
for (auto p : putnici) ans=min(ans,putuj(p,C,D,plafon));
if (ans>n) ans=-1;
return ans;
}
/*
5 1000
1 2 3 4 5
0 0 4 4
7 1000
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
10 1000
9 1 2 3 4 5 6 7 8 10
0 0 1 1
1 1 5 5
1 1 6 6
*/
