#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int h[MAXN], prevmx[MAXN], nxtmx[MAXN], idx[MAXN];
vector<vector<int>> dp;
int n;
void init(int N, vector<int> H) {
n = N;
dp.assign(n, vector<int>(n, n));
copy(H.begin(), H.end(), h);
for (int i = 0; i < n; ++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]];
}
}
for (int i = 0; i < n; ++i) {
dp[i][i] = 0;
for (int val = h[i] - 1; val >= 0; --val) {
int j = idx[val];
if (prevmx[j] != -1) {
dp[i][j] = min(dp[i][j], 1 + dp[i][prevmx[j]]);
}
if (nxtmx[j] != -1) {
dp[i][j] = min(dp[i][j], 1 + dp[i][nxtmx[j]]);
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int mncnt = n;
for (int j = C; j <= D; ++j) {
pair<int, int> val{-1, -1};
for (int i = max(prevmx[j] + 1, A); i <= B; ++i) {
val = max(val, {h[i], i});
}
if (val.first == -1) {
continue;
}
// int x = val.first;
// int cnt = 0;
// while (x != j) {
// cnt++;
// if (prevmx[x] == -1 || h[prevmx[x]] > h[j]) {
// x = nxtmx[x];
// } else if (nxtmx[x] == n) {
// x = prevmx[x];
// } else if (h[prevmx[x]] > h[nxtmx[x]]) {
// x = prevmx[x];
// } else {
// x = nxtmx[x];
// }
// }
mncnt = min(mncnt, dp[j][val.first]);
}
return mncnt == n ? -1 : mncnt;
}
#ifdef LOCAL
int main() {
init(7, {3, 2, 1, 6, 4, 5, 7});
cout << minimum_jumps(1, 1, 6, 6) << '\n';
cout << minimum_jumps(1, 3, 5, 6) << '\n';
cout << minimum_jumps(0, 1, 2, 2) << '\n';
return 0;
}
#endif
