#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int lg = 22;
int h[maxn];
vector<int>g[maxn];
int rev[maxn];
int n;
int opt[maxn][lg];
int nopt[maxn][lg];
int l[maxn][lg];
int r[maxn][lg];
struct segTree{
int *st;
int n;
vector<int>ar;
void rupdate(int l, int r, int ind, int i){
if(i<l||i>r){
return;
}
if(l==r){
st[ind]=i;
return;
}
int mid = (l+r)/2;
rupdate(l,mid,ind*2+1,i);
rupdate(mid+1,r,ind*2+2,i);
if(ar[st[ind*2+1]]>ar[st[2*ind+2]]){
st[ind]=st[ind*2+1];
}
else{
st[ind]=st[ind*2+2];
}
}
segTree(int siz, int arr[]){
int x = ceil(log2(siz));
x++;
st=new int[(1<<x)];
fill(st,st+(1<<x),0);
n=siz-1;
for(int i = 0;i<siz;i++){
ar.push_back(arr[i]);
}
for(int i = 0;i<siz;i++){
rupdate(0,n,0,i);
}
}
int rquery(int l, int r, int s, int e, int ind){
if(e<l||s>r){
return -1;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
int lef = rquery(l,mid,s,e,ind*2+1);
int rig = rquery(mid+1,r,s,e,ind*2+2);
if(lef==-1){
return rig;
}
if(rig==-1){
return lef;
}
if(ar[lef]>ar[rig]){
return lef;
}
else{
return rig;
}
}
int query(int l, int r){
return rquery(0,n,l,r,0);
}
};
segTree st(maxn,h);
void init(int N, vector<int> H) {
n=N;
for(int i = 0;i<n;i++){
h[i]--;
h[i]=H[i];
rev[h[i]-1]=i;
}
st=segTree(n,h);
for(int i = 0;i<n;i++){
fill(opt[i],opt[i]+lg,-1);
fill(nopt[i],nopt[i]+lg,-1);
fill(l[i],l[i]+lg,-1);
fill(r[i],r[i]+lg,-1);
}
set<int>inds;
for(int i = n-1;i>=0;i--){
int ind = rev[i];
if(inds.size()){
auto it = inds.lower_bound(ind);
int lef = -1;
int rig = -1;
if(it!=inds.end()){
g[ind].push_back(*it);
rig=*it;
}
if(it!=inds.begin()){
it--;
g[ind].push_back(*it);
lef=*it;
}
l[ind][0]=lef;
r[ind][0]=rig;
for(int i = 1;i<lg;i++){
if(l[ind][i-1]!=-1){
l[ind][i]=l[l[ind][i-1]][i-1];
}
else{
l[ind][i]=-1;
}
if(r[ind][i-1]!=-1){
r[ind][i]=r[r[ind][i-1]][i-1];
}
else{
r[ind][i]=-1;
}
}
if(lef==-1&&rig!=-1){
//opt and nopt both go right
opt[ind][0]=rig;
nopt[ind][0]=rig;
for(int i = 1;i<lg;i++){
if(opt[ind][i-1]!=-1){
opt[ind][i]=opt[opt[ind][i-1]][i-1];
}
if(nopt[ind][i-1]!=-1)
nopt[ind][i]=nopt[nopt[ind][i-1]][i-1];
}
}
if(lef!=-1&&rig==-1){
//opt and nopt both go left
opt[ind][0]=lef;
nopt[ind][0]=lef;
for(int i = 1;i<lg;i++){
if(opt[ind][i-1]!=-1){
opt[ind][i]=opt[opt[ind][i-1]][i-1];
}
if(nopt[ind][i-1]!=-1)
nopt[ind][i]=nopt[nopt[ind][i-1]][i-1];
}
}
if(lef!=-1&&rig!=-1){
//now must see
if(h[lef]<h[rig]){
swap(lef,rig);
}
//now lef is opt rig is nopt
opt[ind][0]=lef;
nopt[ind][0]=rig;
for(int i = 1;i<lg;i++){
if(opt[ind][i-1]!=-1){
opt[ind][i]=opt[opt[ind][i-1]][i-1];
}
if(nopt[ind][i-1]!=-1)
nopt[ind][i]=nopt[nopt[ind][i-1]][i-1];
}
}
}
inds.insert(rev[i]);
}
//graph creation done
//kth ancestor shenanigans done
}
int minimum_jumps(int a, int b, int c, int d) {
int ans = 0;
if(b==c-1){
if(r[b][0]<=d&&r[b][0]!=-1){
return 1;
}
else{
return -1;
}
}
int middle_max = st.query(b+1,c-1);
//cout << "middle max: " << middle_max << "\n";
int s = b;
for(int i = lg-1;i>=0;i--){
if(l[s][i]>=a&&h[l[s][i]]<h[middle_max]){
s=l[s][i];
}
}
//cout << "s: " << s << "\n";
int cur = s;
//cur -> midmax -> c-d
//cur -> smth>midmax -> c-d
//smth is basically try to reach midmax with opt then go left and right again
for(int i = lg-1;i>=0;i--){
int nx = opt[cur][i];
if(nx!=-1&&h[nx]<h[middle_max]){
if(i&&opt[cur][i]==opt[cur][i-1])
continue;
cur=nx;
//cout << "gone to: " << cur << "\n";
ans+=(1<<i);
//cout << "h\n";
}
}
if(opt[cur][0]==middle_max){
ans++;
cur=opt[cur][0];
}
int temp = 1e9;
if(l[cur][0]!=-1&&r[l[cur][0]][0]!=-1&&r[l[cur][0]][0]<=d){
temp=ans+2;
}
for(int i = lg-1;i>=0;i--){
int nx = nopt[cur][i];
if(nx!=-1&&nx<c&&nopt[cur][i]!=cur&&nopt[cur][i]!=-1){
if(i&&nopt[cur][i]==nopt[cur][i-1])
continue;
cur=nx;
//cout << "here " << i << " " << nx << "\n";
ans+=(1<<i);
}
}
cur=nopt[cur][0];
ans++;
if(cur>=c&&cur<=d){
return min(ans,temp);
}
return -1;
}
