#include<bits/stdc++.h>
#include "jumps.h"
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 2e5 + 23;
const int LOG = 20;
const int inf = 2e9;
#define F first
#define S second
#define pb push_back
#define kill(x) cout<<x<<endl, exit(0);
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lc (v << 1)
#define rc ((v<<1) |1)
int n;
int a[N];
int le[LOG][N], ri[LOG][N], hi[LOG][N];
void init(int nn, vector<int> h) {
n = nn;
// 0 -> 1
for(int i = 1; i<= n ; i++) a[i] = h[i-1];
stack<int> st;
for(int i = 1; i<= n ;i ++) {
while(sz(st) && a[st.top()] < a[i]) st.pop();
if(sz(st)) le[0][i] = st.top();
else le[0][i] = i;
st.push(i);
} while(sz(st)) st.pop();
for(int i = n ; i >= 1;i --) {
while(sz(st) && a[st.top()] < a[i]) st.pop();
if(sz(st)) ri[0][i] = st.top();
else ri[0][i] = i;
if(a[ri[0][i]] > a[le[0][i]]) hi[0][i] = ri[0][i]; else hi[0][i] = le[0][i];
st.push(i);
}
for(int i = 1; i < LOG; i ++) {
for(int j = 1; j<= n ; j ++) {
le[i][j] = le[i-1][le[i-1][j]];
ri[i][j] = ri[i-1][ri[i-1][j]];
hi[i][j] = hi[i-1][hi[i-1][j]];
}
}
}
int gmx(int l,int r,int bound) {
// bozorg tarin yaroo ke az bound camtare ve choon mikhaim breim rast bayad az rast shoroo konim
if(a[r] >= bound) return -1;
for(int i = LOG-1; i >= 0 ;i --) {
if(le[i][r] >= l && a[le[i][r]] < bound) r = le[i][r];
}
return r;
}
int minimum_jumps(int A, int B, int C, int D) {
// 0 -> 1
A++,B++,C++,D++;
int finalboss = gmx(C,D,inf);
// shoroo bayad az finalboss kamtar bashe mantegan
int start = gmx(A,B,a[finalboss]);
// age shoroo peyda nashod
if(start == -1) return -1;
// ye harekat bitch
if(abs(B-C) == 1) return 1;
// vasat ye koskeshe oon balast
int vasat = gmx(B+1,C-1,inf);
// age vasati dige asan ejaze nadad( kiram dahanesh)
if(a[vasat] > a[finalboss]) return -1;
// age bache goli bood
if(a[vasat] < a[start]) return 1;
// ta jaii ke mitooni ziad sho ta be vasat beresi
int ans=0;
for(int i = LOG-1; i>=0 ;i --) {
if(a[hi[i][start]] <= a[vasat]) start = hi[i][start], ans += (1 << i);
}
// residimo residim
if(vasat == start) return ans +1;
if(a[hi[0][start]] < a[finalboss]) return ans + 2;
for(int i = LOG-1; i>= 0 ; i--) {
if(ri[i][start] < C) start = ri[i][start], ans += (1<<i);
}
return ans +1;
}
