#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+10;
const int LOG = 20;
const int MAXA = 1e6;
const int INF = 2e9;
int n, h[MAXN];
int le[MAXN], ri[MAXN], anc[MAXN][LOG+5];
int up[MAXN][LOG+5], dw[MAXN][LOG+5];
pii mx[MAXN][LOG+5];
pii MX(int le, int ri){
if(le > ri) return pii(-INF, 0);
int len = log2(ri-le+1);
return max(mx[le][len], mx[ri-(1<<len)+1][len]);
}
void init(int N, std::vector<int> H) {
n = N;
for(int i=1; i<=n; i++){
h[i] = H[i-1];
mx[i][0] = {h[i], i};
}
for(int j=1; j<LOG; j++){
for(int i=1; i+(1<<j)-1<=n; i++){
mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
}
h[0] = h[n+1] = -INF;
ri[n+1] = n+1;
for(int j=0; j<LOG; j++)
for(int i=0; i<=n+1; i++)
anc[i][j] = up[i][j] = n+1,
dw[i][j] = 0;
vector <pii> vec;
for(int i=n; i>=1; i--){
while(!vec.empty() && h[i] > vec.back().fi) vec.pop_back();
if(!vec.empty()){
ri[i] = vec.back().se;
// cout << i << ' ' << vec.back().se << " pp\n";
} else ri[i] = n+1;
up[i][0] = ri[i];
vec.pb({h[i], i});
}
vec.clear();
for(int i=1; i<=n; i++){
while(!vec.empty() && h[i] > vec.back().fi) vec.pop_back();
if(!vec.empty()){
le[i] = vec.back().se;
// cout << i << ' ' << vec.back().se << " pp\n";
} else le[i] = 0;
dw[i][0] = le[i];
vec.pb({h[i], i});
}
for(int i=1; i<=n; i++){
if(h[le[i]] > h[ri[i]]) anc[i][0] = le[i];
else anc[i][0] = ri[i];
}
for(int j=1; j<LOG; j++)
for(int i=1; i<=n; i++)
anc[i][j] = anc[ anc[i][j-1] ][j-1],
up[i][j] = up[ up[i][j-1] ][j-1],
dw[i][j] = dw[ dw[i][j-1] ][j-1];
}
int cost(int sta, int en){
int tot = 0;
for(int i=LOG-1; i>=0; i--){
if(anc[sta][i]!=n+1 && anc[sta][i]!=0 && h[ anc[sta][i] ] <= h[en]){
sta = anc[sta][i];
tot += (1<<i);
}
}
for(int i=LOG-1; i>=0; i--){
if(up[sta][i]!=n+1 && up[sta][i] <= en){
sta = up[sta][i];
tot += (1<<i);
}
}
if(sta == en) return tot;
return INF;
}
int minimum_jumps(int A, int B, int C, int D) {
// goto right
A++; B++; C++; D++;
if(B == C-1){
if(C<=ri[B] && ri[B]<=D) return 1;
return -1;
}
int mx = MX(B+1, C-1).fi;
int jump = 0, idxj = 0;
if(MX(A, B).fi > mx){ // bisa langsung
int l=A, r=B, mid=0, cnt=A;
while(l<=r){ // cari yg paling kanan lebih dr mx
mid = md;
if(MX(mid, B).fi > mx) l = mid+1, cnt = mid;
else r = mid-1;
}
jump = 0; idxj = cnt;
} else { // harus ke kiri dulu
int nw = MX(A, B).se; // dari range max
int l=1, r=A-1, mid=0, cnt=0;
while(l<=r){ // paling kanan yg more
mid = md;
if(MX(mid, B).fi > mx) l = mid+1, cnt = mid;
else r = mid-1;
}
// harus ke cnt
for(int i=LOG-1; i>=0; i--){ // ke kiri
if(anc[nw][i]!=n+1 && anc[nw][i]!=0 &&
h[ anc[nw][i] ] <= h[cnt]){ // ke cnt
nw = anc[nw][i]; jump += (1<<i);
}
}
idxj = cnt;
}
// cout << idxj << " idx\n";
// cout << jump << " jump\n";
int ans = INF;
if(idxj!=0 && idxj!=n+1
&& C<=ri[idxj] && ri[idxj]<=D) ans = jump+1;
int l=A, r=B, mid=0, cnt=B;
while(l<=r){ // cari max range yg < mx
mid = md;
if(MX(mid, B).fi < mx) cnt = mid, r = mid-1;
else l = mid+1;
}
int sta = MX(cnt, B).se;
// cout << sta << " sta\n";
l=C, r=D, mid=0, cnt=C;
while(l<=r){
mid = md;
if(MX(C, mid).fi > mx) cnt = mid, r = mid-1;
else l = mid+1;
}
if(MX(C, D).fi < mx) return -1; // gk bisa ke sana
int en = cnt;
ans = min(ans, cost(sta, en));
return (ans > n ? -1 : ans);
}
