#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int h[MAXN], prevmx[MAXN], nxtmx[MAXN], jmpup[MAXN][20], jmpright[MAXN][20], idx[MAXN + 1];
int n;
struct segtree {
int n;
vector<pair<int, int>> seg;
segtree() = default;
segtree(int n) : n(n), seg(2 * n, {-1, -1}) {};
void update(int i, pair<int, int> val) {
i += n;
seg[i] = max(seg[i], val);
for (; i >>= 1;) {
seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
}
pair<int, int> query(int l, int r) {
pair<int, int> ans = {-1, -1};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
ans = max(ans, seg[l++]);
}
if (r & 1) {
ans = max(ans, seg[--r]);
}
}
return ans;
}
};
segtree st;
void init(int N, vector<int> H) {
n = N;
st = n;
copy(H.begin(), H.end(), h);
for (int i = 0; i < n; ++i) {
st.update(i, {h[i], i});
idx[h[i]] = i;
}
for (int i = 0; i < n; ++i) {
prevmx[i] = i - 1;
while (prevmx[i] != -1 && h[prevmx[i]] <= h[i]) {
prevmx[i] = prevmx[prevmx[i]];
}
}
for (int i = n - 1; i >= 0; --i) {
nxtmx[i] = i + 1;
while (nxtmx[i] < n && h[nxtmx[i]] <= h[i]) {
nxtmx[i] = nxtmx[nxtmx[i]];
}
}
memset(jmpup, -1, sizeof jmpup);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 20; ++j) {
jmpright[i][j] = n;
}
}
for (int val = n; val >= 1; --val) {
int i = idx[val];
auto nxt = [&](int x) {
if (prevmx[x] == -1 && nxtmx[x] == n) {
return -1;
} else if (prevmx[x] == -1) {
return nxtmx[x];
} else if (nxtmx[x] == n) {
return prevmx[x];
} else if (h[prevmx[x]] > h[nxtmx[x]]) {
return prevmx[x];
} else {
return nxtmx[x];
}
};
jmpup[i][0] = nxt(i);
int j = 0;
while (jmpup[i][j] != -1) {
jmpup[i][j + 1] = jmpup[jmpup[i][j]][j];
j++;
}
jmpright[i][0] = nxtmx[i];
j = 0;
while (jmpright[i][j] < n) {
jmpright[i][j + 1] = jmpright[jmpright[i][j]][j];
j++;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int mncnt = n;
for (int i = C; i <= D; ++i) {
pair<int, int> val = st.query(max(prevmx[i] + 1, A), B + 1);
if (val.first == -1) {
continue;
}
int x = val.second;
int cnt = 0;
while (jmpup[x][0] != -1 && h[jmpup[x][0]] < h[i]) {
int j = 0;
for (; 1 << j < n; ++j) {
if (jmpup[x][j] == -1 || h[jmpup[x][j]] >= h[i]) {
break;
}
}
cnt += 1 << (--j);
x = jmpup[x][j];
}
while (x != i) {
cnt++;
x = jmpright[x][0];
}
// while (jmpright[x][0] < n && h[jmpright[x][0]] < h[i]) {
// int j = 0;
// for (; 1 << j < n; ++j) {
// if (jmpright[x][j] == -1 || h[jmpright[x][j]] >= h[i]) {
// break;
// }
// }
// cnt += 1 << (--j);
// x = jmpright[x][j];
// }
cnt++;
mncnt = min(mncnt, cnt);
}
return mncnt == n ? -1 : mncnt;
}
#ifndef EVAL
int main() {
init(7, {3, 2, 1, 6, 4, 5, 7});
cout << minimum_jumps(4, 4, 6, 6) << '\n';
cout << minimum_jumps(1, 3, 5, 6) << '\n';
cout << minimum_jumps(0, 0, 2, 2) << '\n';
// init(7, {4, 1, 7, 6, 3, 5, 2});
// cout << minimum_jumps(1, 2, 3, 6) << '\n';
// cout << minimum_jumps(0, 3, 4, 6) << '\n';
// cout << minimum_jumps(0, 1, 2, 2) << '\n';
return 0;
}
#endif
