#include "bits/stdc++.h"
#include "jumps.h"
// #include "stub.cpp"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
#define mm make_pair
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int INF = 1e9;
const int N = 2e5+5;
const int LOG = 20;
int a[N], sp[N][LOG], spl[N][LOG], spr[N][LOG];
void init(int n, vector<int> A){
for(int i = 0; i < n; ++i){
a[i]=A[i];
for(int j = 0; j < LOG; ++j)
sp[i][j]=spl[i][j]=spr[i][j]=-1;
}
stack<int> st;
for(int i = 0; i < n; ++i){
while(!st.empty() and a[st.top()]<a[i])
st.pop();
if(!st.empty())
spl[i][0]=st.top();
st.push(i);
}
while(!st.empty())
st.pop();
for(int i = n-1; i >= 0; --i){
while(!st.empty() and a[st.top()]<a[i])
st.pop();
if(!st.empty()){
spr[i][0]=st.top();
if(spl[i][0]==-1 or a[spl[i][0]]<a[spr[i][0]])
sp[i][0]=spr[i][0];
else
sp[i][0]=spl[i][0];
}
else
sp[i][0]=spl[i][0];
st.push(i);
}
for(int j = 1; j < LOG; ++j)
for(int i = 0; i < n; ++i){
if(~sp[i][j-1])
sp[i][j]=sp[sp[i][j-1]][j-1];
if(~spl[i][j-1])
spl[i][j]=spl[spl[i][j-1]][j-1];
if(~spr[i][j-1])
spr[i][j]=spr[spr[i][j-1]][j-1];
}
}
int minimum_jumps(int A, int b, int c, int d){
assert(c==d);
for(int j = LOG-1; j >= 0; --j)
if(spl[b][j]>=A and a[spl[b][j]]<a[c])
b=spl[b][j];
int answer=0;
for(int j = LOG-1; j >= 0; --j)
if(~sp[b][j] and a[sp[b][j]]<a[c])
b=sp[b][j], answer+=(1<<j);
for(int j = LOG-1; j >= 0; --j)
if(~spr[b][j] and a[spr[b][j]]<a[c])
b=spr[b][j], answer+=(1<<j);
if(spr[b][0]!=c)
answer=-1;
else
answer++;
return answer;
}
