#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back
#define ALL(x) x.begin(), x.end()
const int maxn = 2e5 + 10, INF = 1e9 + 7;
int n, h[maxn], tree[maxn * 4],
jump_mn[maxn][20], jump_mx[maxn][20], jump_right[maxn][20];
vector<pii> mst[maxn * 4];
void build(int tl = 0, int tr = maxn, int i = 1){
if (tl == tr){
tree[i] = tl;
mst[i].PB({h[tl], tl});
return;
}
int tm = (tl + tr) / 2;
build(tl, tm, i * 2); build(tm + 1, tr, i * 2 + 1);
tree[i] = (h[tree[i * 2]] > h[tree[i * 2 + 1]] ?
tree[i * 2] : tree[i * 2 + 1]);
merge(ALL(mst[i * 2]), ALL(mst[i * 2 + 1]), back_inserter(mst[i]));
}
int query(int l, int r, int tl = 0, int tr = maxn, int i = 1){
if (l > tr || tl > r) return maxn - 1;
if (l <= tl && tr <= r) return tree[i];
int tm = (tl + tr) / 2;
int left = query(l, r, tl, tm, i * 2),
right = query(l, r, tm + 1, tr, i * 2 + 1);
if (h[left] > h[right]) return left;
return right;
}
int get(int l, int r, int x, int tl = 0, int tr = maxn, int i = 1){
if (l > tr || tl > r) return maxn - 1;
if (l <= tl && tr <= r){
int idx = upper_bound(ALL(mst[i]), make_pair(x, INF)) - mst[i].begin() - 1;
if (idx == -1) return maxn - 1;
return mst[i][idx].S;
}
int tm = (tl + tr) / 2;
int left = get(l, r, x, tl, tm, i * 2),
right = get(l, r, x, tm + 1, tr, i * 2 + 1);
if (h[left] > h[right]) return left;
return right;
}
int go_right(int s, int c, int d){
int re = 0;
for (int p = 19; p >= 0; p--){
if (jump_right[s][p] < c) re += (1<<p), s = jump_right[s][p];
}
if (c <= jump_right[s][0] && jump_right[s][0] <= d) return re + 1;
return INF;
}
int solve(int a, int b, int c, int d){
int e = query(c, d), mid = query(b, c);
int s = get(a, b, h[e]);
if (s >= n) return INF;
int re = 0;
for (int p = 19; p >= 0; p--){
if (h[jump_mx[s][p]] < h[mid]) re += (1<<p), s = jump_mx[s][p];
}
return re + min(go_right(s, c, d),
go_right(jump_mx[s][0], c, d) + 1);
}
void init(int N, vector<int> H){
fill(h, h + maxn, INF); h[maxn - 1] = -1;
n = N;
FOR(i, n) h[i] = H[i];
build();
stack<int> s;
for (int i = n - 1; i >= 0; i--){
while (!s.empty() && h[s.top()] < h[i]) s.pop();
int x = (s.empty() ? i : s.top());
jump_mx[i][0] = jump_mn[i][0] = x;
jump_right[i][0] = x;
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = 0; i < n; i++){
while (!s.empty() && h[s.top()] < h[i]) s.pop();
int x = (s.empty() ? i : s.top());
if (h[x] > h[jump_mx[i][0]] && x != i) jump_mx[i][0] = x;
if (h[x] < h[jump_mn[i][0]] && x != i) jump_mn[i][0] = x;
s.push(i);
}
for (int p = 1; p < 20; p++){
FOR(i, n){
jump_mx[i][p] = jump_mx[jump_mx[i][p - 1]][p - 1];
jump_mn[i][p] = jump_mn[jump_mn[i][p - 1]][p - 1];
jump_right[i][p] = jump_right[jump_right[i][p - 1]][p - 1];
}
}
}
int minimum_jumps(int a, int b, int c, int d){
int re = solve(a, b, c, d);
return (re < INF ? re : -1);
}
