#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int N=200050; const int LOG=25; int a[N],l[N],r[N],mn[N][LOG],mx[N][LOG],L[N][LOG],st[N][LOG]; int getmx(int l,int r){ int res=0; for(int i=LOG-1;~i;i--)if(l+(1<<i)-1<=r)res=max(res,st[l][i]),l+=(1<<i); return res; } void init(int n,vector<int> h){ for(int i=1;i<=n;i++)a[i]=h[i-1],st[i][0]=a[i]; for(int j=1;j<LOG;j++)for(int i=1;i+(1<<j)<=n+1;i++)st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); stack<int> stk; for(int i=1;i<=n;i++){ while(!stk.empty()&&a[stk.top()]<a[i])stk.pop(); if(!stk.empty())l[i]=stk.top(); else l[i]=0; stk.push(i); } while(stk.size())stk.pop(); for(int i=n;i>=1;i--){ while(!stk.empty()&&a[stk.top()]<a[i])stk.pop(); if(!stk.empty())r[i]=stk.top(); else r[i]=0; stk.push(i); } for(int i=1;i<=n;i++){ if(r[i]!=0&&(l[i]==0||a[l[i]]>a[r[i]]))mn[i][0]=r[i]; else mn[i][0]=l[i]; if(r[i]!=0&&(l[i]==0||a[l[i]]<a[r[i]]))mx[i][0]=r[i]; else mx[i][0]=l[i]; L[i][0]=l[i]; } // for(int i=1;i<=n;i++){ // printf("i:%d l:%d r:%d\n",i,l[i],r[i]); // } for(int j=1;j<LOG;j++){ for(int i=1;i<=n;i++){ mn[i][j]=mn[mn[i][j-1]][j-1]; mx[i][j]=mx[mx[i][j-1]][j-1]; L[i][j]=L[L[i][j-1]][j-1]; } } } int minimum_jumps(int A,int B,int C,int D){ A++;B++;C++;D++; int x=getmx(C,D),pos=B; for(int i=LOG-1;~i;i--)if(L[pos][i]>=A&&a[L[pos][i]]<x)pos=L[pos][i]; // printf("pos: %d x:%d a[pos]:%d\n",pos,x,a[pos]); if(a[pos]>x)return -1; int ans=0; for(int i=LOG-1;~i;i--){ if(mx[pos][i]>0&&mx[pos][i]<=C&&a[mx[pos][i]]<=x)pos=mx[pos][i],ans+=(1<<i); if(pos>=C)return ans; } // if(mn[pos][0]==0||mn[pos][0]>D)return -1; // if(mx[pos][0]>=C&&mx[pos][0]<=D)return ans+1; for(int i=LOG-1;~i;i--){ if(mn[pos][i]>0&&mn[pos][i]<=C)pos=mn[pos][i],ans+=(1<<i); if(pos>=C)return ans; } if(mn[pos][0]>=C&&mn[pos][0]<=D)return ans+1; return -1; } //int main(){ // int d; // scanf("%d",&d); // vector<int> A(d); // for(int i=0;i<d;i++)scanf("%d",&A[i]); // init(d,A); // printf("%d\n",minimum_jumps(4,4,6,6)); // printf("%d\n",minimum_jumps(1,3,5,6)); // printf("%d\n",minimum_jumps(0,1,2,2)); // return 0; //} /* 7 3 2 1 6 4 5 7 */