#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcount(n)
#define clean fflush(stdout)
//const ll mod = (ll) 998244353;
const ll mod = (ll) 1e9 + 7;
const ll maxn = (ll)1e8 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
//const ll INF = (ll)1e18;
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};
const ll N = 2e5 + 5;
ll a[N], n, p[N];
ll lft[N] , rght[N];
ll par[N][20], L[N][20], R[N][20];
struct seg_tree{
struct typo{
ll mx;
void setup(ll _sum){
mx = _sum;
}
};
vector < typo > b;
ll n;
void init(ll l, ll r, ll node){
b[node].setup(a[l]);
return;
}
typo merge(typo a, typo b){
typo c;
c.mx = max(a.mx, b.mx);
return c;
}
void build(ll l, ll r, ll node){
if(l == r){
init(l,r,node);
return;
}
ll mid = (l + r)/2;
ll n1 = 2*node;
ll n2 = n1 + 1;
build(l, mid , n1);
build(mid+1, r, n2);
b[node] = merge(b[n1] , b[n2]);
return;
}
void build(ll _n){
n = _n;
b.resize(4*n);
build(1,n,1); // optional
}
typo get(ll l, ll r, ll node, ll x, ll y){
if(y < l || x > r) return {0};
if(x <= l && y >= r){
return b[node];
}
ll mid = (l + r)/2;
ll n1 = 2*node;
ll n2 = n1 + 1;
return merge(get(l , mid , n1 , x , y) , get(mid + 1, r , n2 , x , y));
}
ll get(ll l, ll r){
return get(1,n,1,l,r).mx;
}
/* Final Check!!!
1. Typo, Okay?
2. Init Okay? (Build!!)
3. Merge, Okay?
4. Lazy Needed ? YES | NO (if NO, REMOVE anything related to lazy prop)
5. Dummy?
6. Check Update, Get, etc function's Merge, Lazy Prop , Init :D
7, Even after a WA, check for possible Out Of Bound/MLE/RE cases
*/
}T;
void init(int _n, std::vector<int> H) {
n = _n;
for(ll i = 1; i <= n; i++){
a[i] = H[i - 1];
p[a[i]] = i;
}
a[0] = a[n + 1] = n + 1;
stack < ll > st;
st.push(0);
for(ll i = 1; i <= n; i++){
while(st.size() && a[st.top()] < a[i]) st.pop();
lft[i] = st.top();
st.push(i);
}
while(st.size()) st.pop();
st.push(n + 1);
for(ll i = n; i >= 1; i--){
while(st.size() && a[st.top()] < a[i]) st.pop();
rght[i] = st.top();
st.push(i);
}
for(ll i = 0; i < 20; i++){
par[0][i] = L[0][i] = R[0][i] = 0;
par[n+1][i] = L[n+1][i] = R[n+1][i] = n+1;
}
for(ll i = 1; i <= n; i++){
if(a[lft[i]] > a[rght[i]]) par[i][0] = lft[i];
else par[i][0] = rght[i];
L[i][0] = lft[i];
R[i][0] = rght[i];
}
for(ll j = 1; j < 20; j++){
for(ll i = 1; i <= n; i++){
par[i][j] = par[par[i][j - 1]][j - 1];
L[i][j] = L[L[i][j-1]][j-1];
R[i][j] = R[R[i][j-1]][j-1];
}
}
T.build(n);
return;
}
ll apply(ll x, ll C, ll D){
ll res = 0;
for(ll i = 19; i >= 0; i--){
if(R[x][i] < C) x = R[x][i], res += (1 << i);
}
if(rght[x] <= D) res++;
else res = 1e9;
return res;
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
ll e = T.get(C,D);
if(a[B] > e) return -1;
ll x = B;
for(ll i = 19; i >= 0; i--){
if(A <= L[x][i] && a[L[x][i]] < e) x = L[x][i];
}
ll prob = T.get(x, C-1);
if(prob > e) return -1;
ll ans = 0;
for(ll i = 19; i >= 0; i--){
if(a[par[x][i]] <= prob){
ans += (1 << i);
x = par[x][i];
}
}
ll k = apply(x, C, D);
if(lft[x]) k = min(k, 1 + apply(lft[x], C,D));
if(k > n) return -1;
return ans + k;
}
