#include "jumps.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;
int h[mxn];
int n;
int dp1[20][mxn], dp2[20][mxn];
int prv[mxn], nxt[mxn];
int pos[mxn] = {};
struct segtree {
vector<int> tree[4*mxn];
int mx[4 * mxn];
void build(int node,int b,int e) {
if(b==e) {
tree[node].push_back(h[b]);
mx[node] = h[b];
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
build(left,b,mid);
build(right,mid+1,e);
mx[node] = max(mx[left], mx[right]);
tree[node].resize(e - b + 1);
merge(tree[left].begin(), tree[left].end(), tree[right].begin(), tree[right].end(), tree[node].begin());
}
int query(int node, int b, int e, int l, int r, int v) {
if(b > r || e < l) return 0;
if(b >= l && e <= r) {
int p = lower_bound(tree[node].begin(), tree[node].end(), v) - tree[node].begin() - 1;
if(p < 0) return 0;
return tree[node][p];
}
int mid = b + e >> 1;
int left = node << 1;
int right = left | 1;
return max(query(left, b, mid, l, r, v), query(right, mid + 1, e, l, r, v));
}
int get_ind(int node, int b, int e, int p, int v) {
if(b > p) return 0;
if(mx[node] <= v) return 0;
if(b == e) return b;
int mid = b + e >> 1;
int left = node << 1;
int right = left | 1;
int res = get_ind(right, mid + 1, e, p, v);
if(res) return res;
return get_ind(left, b, mid, p, v);
}
int rmq(int node, int b, int e, int l, int r) {
if(b > r || e < l) return 0;
if(b >= l && e <= r) return mx[node];
int mid = b + e >> 1;
int left = node << 1;
int right = left | 1;
return max(rmq(left, b, mid, l, r), rmq(right, mid + 1, e, l, r));
}
} st;
pii go1(int p, int v) {
int cost = 0;
for(int i = 19; i >= 0; i--) {
if(h[dp1[i][p]] <= v) {
p = dp1[i][p];
cost += 1 << i;
}
}
return {p, cost};
}
pii go2(int p, int v) {
int cost = 0;
for(int i = 19; i >= 0; i--) {
if(h[dp2[i][p]] <= v) {
p = dp2[i][p];
cost += 1 << i;
}
}
return {p, cost};
}
void init(int N, vector<int> H) {
n = N;
for(int i = 1; i <= n; i++) {
h[i] = H[i - 1];
pos[h[i]] = i;
}
st.build(1, 1, n);
h[0] = inf;
stack<int> st;
st.push(0);
for(int i = 1; i <= n; i++) {
while(h[st.top()] <= h[i]) st.pop();
prv[i] = st.top();
st.push(i);
}
while(!st.empty()) st.pop();
h[n + 1] = inf;
st.push(n + 1);
for(int i = n; i >= 1; i--) {
while(h[st.top()] <= h[i]) st.pop();
nxt[i] = st.top();
st.push(i);
}
for(int i = 1; i <= n; i++) {
if(h[prv[i]] > h[nxt[i]]) {
dp1[0][i] = prv[i];
dp2[0][i] = nxt[i];
} else {
dp1[0][i] = nxt[i];
dp2[0][i] = prv[i];
}
}
for(int i = 1; i < 20; i++) {
for(int j = 1; j <= n; j++) {
dp1[i][j] = dp1[i - 1][dp1[i - 1][j]];
dp2[i][j] = dp2[i - 1][dp2[i - 1][j]];
}
}
}
int fixed_both(int A, int B) {
auto [x, cost1] = go1(A, h[B]);
auto [y, cost2] = go2(x, h[B]);
if(y == B) return cost1 + cost2;
return inf;
}
int fixed_target(int A, int B, int C) {
int id = st.get_ind(1, 1, n, B, h[C]);
int v = st.query(1, 1, n, max(A, id + 1), B, h[C]);
if(v == 0) return inf;
int p = pos[v];
return fixed_both(p, C);
}
int minimum_jumps(int A, int B, int C, int D) {
A++;
B++;
C++;
D++;
int mm = st.rmq(1, 1, n, B + 1, C - 1);
int mp = pos[mm];
int ans = inf;
if(mm != 0 && nxt[mp] <= D) ans = fixed_target(A, B, mp) + 1;
int lp = st.get_ind(1, 1, n, B, mm);
if(lp >= A && nxt[lp] <= D) ans = 1;
else if(lp != 0 && nxt[lp] <= D) {
int cmx = st.rmq(1, 1, n, A, B);
ans = min(ans, fixed_both(pos[cmx], lp) + 1);
}
if(ans >= inf) return -1;
return ans;
}
