#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> H;
map<int, int> revH;
vector<int> mxpar, mnpar;
vector<int> prefmx, suffmx;
vector<vector<int>> up;
set<int> allmx;
struct Mxtree {
int n;
vector<int> tree;
// Mxtree(vector<int>& a){
// int n = 1;
// while (n < a.size()) n *= 2;
// tree.assign(2*n, 0);
// for (int i=0; i<a.size(); i++) tree[i+n] = a[i];
// for (int i=n-1; i>0; i--) tree[i] = max(tree[i*2], tree[i*2+1]);
// }
void build(vector<int>& a){
n = 1;
while (n < a.size()) n *= 2;
tree.assign(2*n, 0);
for (int i=0; i<a.size(); i++) tree[i+n] = a[i];
for (int i=n-1; i>0; i--) tree[i] = max(tree[i*2], tree[i*2+1]);
}
void update(int x, int val){
x += n;
tree[x] = val;
while (x > 1){
x /= 2;
tree[x] = max(tree[2*x], tree[2*x+1]);
}
}
int query(int l, int r){
l += n; r += n;
int ret = -1;
while (l < r){
if (l & 1) ret = max(ret, tree[l++]);
if (r & 1) ret = max(ret, tree[--r]);
l /= 2; r /= 2;
}
return ret;
}
};
Mxtree st;
struct Lift {
int n, LOG;
vector<vector<int>> up;
void build(vector<int>& a){
n = a.size();
LOG = __lg(n);
up.assign(LOG+1, vector<int>(n, -1));
for (int i=0; i<n; i++){
up[0][i] = a[i];
//cout << up[0][i] << ' ';
}
//cout << endl;
for (int k=1; k<=LOG; k++){
for (int i=0; i<n; i++){
if (up[k-1][i] != -1 && up[k-1][up[k-1][i]] != -1) up[k][i] = up[k-1][up[k-1][i]];
//cout << up[k][i] << ' ';
}
//cout << endl;
}
}
pair<int, int> query(int x, int val){
int ret = 0;
for (int k=LOG; k>=0; k--){
if (up[k][x] != -1 && H[up[k][x]] <= val){
x = up[k][x];
ret += 1<<k;
}
//cout << "X: " << x << endl;
}
return {ret, H[x]};
}
};
Lift mnup, mxup;
void init(int N, vector<int> H_){
mnpar.assign(N, -1); mxpar.assign(N, -1); prefmx.resize(N), suffmx.resize(N); up.assign(__lg(N), vector<int>(N, -1));
H = H_;
for (int i=0; i<N; i++) revH[H[i]] = i;
vector<int> prv(N, -1), nxt(N, -1);
stack<int> stk;
stk.push(1e9);
for (int i=0; i<N; i++){
while (stk.top() < H[i]) stk.pop();
if (stk.top() != 1e9) prv[i] = revH[stk.top()];
stk.push(H[i]);
//cout << prv[i] << ' ';
}
while (stk.top() != 1e9) stk.pop();
for (int i=N-1; i>=0; i--){
while (stk.top() < H[i]) stk.pop();
if (stk.top() != 1e9) nxt[i] = revH[stk.top()];
stk.push(H[i]);
//cout << nxt[i] << ' ';
}
//cout << endl;
for (int i=0; i<N; i++){
if (prv[i] == -1 && nxt[i] == -1) continue;
else if (prv[i] == -1) mxpar[i] = mnpar[i] = nxt[i];
else if (nxt[i] == -1) mxpar[i] = mnpar[i] = prv[i];
else {
mxpar[i] = prv[i]; mnpar[i] = nxt[i];
if (H[prv[i]] < H[nxt[i]]) swap(mxpar[i], mnpar[i]);
}
}
for (int i=0; i<N; i++) allmx.insert(mxpar[i]);
mnup.build(mnpar);
mxup.build(mxpar);
prefmx[0] = H[0];
for (int i=1; i<N; i++) prefmx[i] = max(prefmx[i-1], H[i]);
suffmx[N-1] = H[N-1];
for (int i=N-2; i>=0; i--) suffmx[i] = max(suffmx[i+1], H[i]);
st.build(H);
//for (int i=0; i<N; i++) cout << st.query(i, i+1) << endl;
}
int minimum_jumps(int A, int B, int C, int D){
int mxend = revH[st.query(C, D+1)];
int mxinter = revH[st.query(B, C)];
if (H[mxinter] > H[mxend]) return -1;
int mnendv = max(H[mxinter], H[C]);
if (st.query(B, B+1) > H[mxend]) return -1;
int l = A-1, r = B;
while (l+1 < r){
int m = (l+r)/2;
if (st.query(m, B+1) > H[mxend]) l = m;
else r = m;
}
int mxstart = revH[st.query(r, B+1)];
int ans = 0;
auto [moves, val] = mxup.query(mxstart, mnendv);
ans += moves;
int idx = revH[val];
if (C <= idx && idx <= D) return ans;
int best = 1e9;
if (mxpar[idx] != -1){
if (C <= mxpar[idx] && mxpar[idx] <= D) best = min(best, ans+1);
if (H[mxpar[idx]] < H[mxend]) best = min(best, ans+2);
}
auto [add, v] = mnup.query(idx, mnendv);
if (C <= revH[v] && revH[v] <= D) best = min(best, ans+add);
else best = min(best, ans+add+1);
return best;
}
