#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define sz 200005
int n;
vector<int> v;
int dp[sz];
int tree[sz*3];
void Init(int node,int b,int e)
{
if(b==e)
{
tree[node] = v[b];
return ;
}
int lft = node*2;
int rgt = node*2+1;
int mid = (b+e)/2;
Init(lft,b,mid);
Init(rgt,mid+1,e);
tree[node] = max(tree[lft] ,tree[rgt]);
}
int Query(int node,int b,int e,int i,int j)
{
if(i>e || j<b)
return 0;
if(b>=i && e<=j)
return tree[node];
int mid = (b+e)/2;
int sum1 = Query(node*2,b,mid,i,j);
int sum2 = Query(node*2+1,mid+1,e,i,j);
return max(sum1,sum2);
}
void init(int N, std::vector<int> H) {
int i;
n = N;
v.push_back(0);
for(i=0;i<N;i++){
v.push_back(H[i]);
}
Init(1,1,n);
}
int FuN(int last,int C,int D)
{
if(last>=C && last<=D){
return 0;
}
if(dp[last]!=-1)
return dp[last];
int ret = 1e9;
int lo=last+1,hi=n,mid,res=-1;
while(lo<=hi)
{
mid = (lo+hi)/2;
if(Query(1,1,n,last+1,mid)>v[last])
{
res = mid;
hi = mid-1;
}
else
lo = mid+1;
}
if(res!=-1)
ret = min(ret,1+FuN(res,C,D));
lo=1,hi=last-1,mid,res=-1;
while(lo<=hi)
{
mid = (lo+hi)/2;
if(Query(1,1,n,mid,last-1)>v[last])
{
res = mid;
lo = mid+1;
}
else
hi = mid-1;
}
if(res!=-1)
ret = min(ret,1+FuN(res,C,D));
return dp[last] = ret;
}
int minimum_jumps(int A, int B, int C, int D) {
memset(dp,-1,sizeof(dp));
int ans=1e9;
A++;
B++;
C++;
D++;
for(int i=A;i<=B;i++){
ans = min(ans,FuN(i,C,D));
}
if(ans==1e9)
ans = -1;
return ans;
}
