#include<bits/stdc++.h>
using namespace std;
int lft[400007],rgt[400007],jmpl[400007][19],jmpg[400007][19],spars[200007][18],pos[200007];
bool czy1=1;
bool odw[400007];
int n;
vector<int>v;
int mx(int a,int b){
int k=b-a+1;
if(k<=0) return -1;
return max(spars[a][__lg(k+1)-1],spars[b+1-(1<<(__lg(k+1)-1))][__lg(k+1)-1]);
}
int furthest_greater(int a1,int b1,int x){
//cout<<"q";
if(mx(a1,b1)<=x) return pos[mx(a1,b1)];
while(a1!=b1){
//cout<<a1<<" "<<b1<<" c ";
int mid=(a1+b1)/2;
if(mx(mid+1,b1)>x) a1=mid+1;
else b1=mid;
}
if(v[a1]>x)return a1;
else return a1-1;
}
void init(int N,vector<int>V){
n=N;
v=V;
while(v.size()<400007)
v.push_back(400006);
stack<int>s;
lft[400006]=400006;
rgt[400006]=400006;
//s.push(n);
for(int i=0;i<n;i++){
pos[v[i]]=i;
lft[i]=400006;
rgt[i]=400006;
}
//return;
for(int i=0;i<n;i++){
if(s.empty() || v[s.top()]>v[i])
s.push(i);
else{
rgt[s.top()]=i;
s.pop();
i--;
}
}
while(s.size()>0) s.pop();
for(int i=n-1;i>=0;i--){
if(s.empty() || v[s.top()]>v[i])
s.push(i);
else{
czy1=0;
lft[s.top()]=i;
s.pop();
i++;
}
}
for(int i=0;i<n;i++){
int pm=lft[i];
if(v[lft[i]]>v[rgt[i]]){
lft[i]=rgt[i];
rgt[i]=pm;
}
jmpg[i][0]=rgt[i];
jmpl[i][0]=lft[i];
spars[i][0]=v[i];
}
jmpl[400006][0]=400006;
jmpg[400006][0]=400006;
for(int i=1;i<19;i++){
for(int j=0;j<n;j++){
jmpl[j][i]=jmpl[jmpl[j][i-1]][i-1];
jmpg[j][i]=jmpg[jmpg[j][i-1]][i-1];
// cout<<jmpg[j][i]<<" ";
}
jmpl[400006][i]=400006;
jmpg[400006][i]=400006;
// cout<<"\n";
}
for(int i=1;i<18;i++){
for(int j=0;j<n+1-(1<<i);j++){
spars[j][i]=max(spars[j][i-1],spars[j+(1<<(i-1))][i-1]);
}
}
//for(int i=0;i<n;i++)
//cout<<lft[i]<<" "<<rgt[i]<<"\n";
}
int minimum_jumps(int a,int b,int c,int d){
if(czy1)
return c-b;
int odp=0;
if(c==d){
int sava=a;
a=pos[mx(furthest_greater(a,b,v[c])+1,b)];
//cout<<a;//<<" "<<furthest_greater(sava,b,c)<<" ";
if(a==-1) return -1;
int akindex=-1;
//int odp=0;
while(v[jmpg[a][akindex+1]]<=v[c])
akindex++;
if(akindex>=0){
odp+=1<<akindex;
//cout<<akindex<<" a ";
//return 0;
//cout<<a<<" ";
a=jmpg[a][akindex];
//cout<<a<<" ";
akindex--;}
while(akindex>=0){
if(v[jmpg[a][akindex]]>v[c]){
akindex--;
continue;
}
odp+=1<<akindex;
a=jmpg[a][akindex];
akindex--;
// cout<<a<<" ";
}
akindex=-1;
while(v[jmpl[a][akindex+1]]<=v[c])
akindex++;
if(akindex>=0){
odp+=1<<akindex;
//cout<<akindex<<" a ";
//return 0;
a=jmpl[a][akindex];
akindex--;}
while(akindex>=0){
if(v[jmpl[a][akindex]]>v[c]){
akindex--;
continue;
}
odp+=1<<akindex;
a=jmpl[a][akindex];
akindex--;
//cout<<a<<" ";
}
if(a!=c)
odp=-1;
return odp;
a=sava;
}
odw[400006]=1;
int ans[n];
for(int i=0;i<n;i++){ odw[i]=0; ans[i]=400007;}
for(int i=a;i<=b;i++) odw[i]=1;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(int i=a;i<=b;i++){
pq.push({0,i});
}
while(!pq.empty()){
pair<int,int>pom=pq.top();
pq.pop();
ans[pom.second]=pom.first;
if(!odw[lft[pom.second]]){
odw[lft[pom.second]]=1;
pq.push({pom.first+1,lft[pom.second]});
}
if(!odw[rgt[pom.second]]){
odw[rgt[pom.second]]=1;
pq.push({pom.first+1,rgt[pom.second]});
}
//return 0;
}
int mn=400007;
for(int i=c;i<=d;i++){
mn=min(mn,ans[i]);
}
if(mn==400007)
mn=-1;
//cout<<ans[11];
//cout<<mn;
return mn;
}
