#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
int a[MAXN], prv[MAXN], nxt[MAXN], n;
int dp[19][MAXN], dp2[19][MAXN], dp3[19][MAXN];
void init (int N, vector <int> h) {
n = N;
for (int i = 0; i < n; i++) a[i + 1] = h[i];
stack <int> cur;
cur.push(1);
for (int i = 2; i <= n; i++) {
while (!cur.empty() && a[i] > a[cur.top()]) {
nxt[cur.top()] = i;
cur.pop();
}
cur.push(i);
}
while (!cur.empty()) {
nxt[cur.top()] = 0;
cur.pop();
}
cur.push(n);
for (int i = n - 1; i >= 1; i--) {
while (!cur.empty() && a[i] > a[cur.top()]) {
prv[cur.top()] = i;
cur.pop();
}
cur.push(i);
}
while (!cur.empty()) {
prv[cur.top()] = 0;
cur.pop();
}
for (int i = 1; i <= n; i++) {
dp2[0][i] = prv[i];
dp3[0][i] = nxt[i];
if (prv[i] && nxt[i] && a[prv[i]] > a[nxt[i]]) {
dp[0][i] = prv[i];
} else if (prv[i] && nxt[i] && a[prv[i]] < a[nxt[i]]) {
dp[0][i] = nxt[i];
}
}
for (int i = 1; i < 19; i++) {
for (int j = 1; j <= n; j++) {
dp2[i][j] = dp2[i - 1][dp2[i - 1][j]];
dp3[i][j] = dp3[i - 1][dp3[i - 1][j]];
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
}
int jump (int a, int b) {
for (int i = 18; i >= 0; i--) {
if (b & (1 << i)) {
a = dp[i][a];
}
}
return a;
}
int jump2 (int a, int b) {
for (int i = 18; i >= 0; i--) {
if (b & (1 << i)) {
a = dp2[i][a];
}
}
return a;
}
int jump3 (int a, int b) {
for (int i = 18; i >= 0; i--) {
if (b & (1 << i)) {
a = dp3[i][a];
}
}
return a;
}
int minimum_jumps (int a, int b, int c, int d) {
a++; b++; c++; d++;
int l = 0, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int x = jump2(b, mid);
if (x == 0 || x < a) {
r = mid - 1; continue;
}
if (!nxt[x] || nxt[x] > d) {
r = mid - 1; continue;
}
l = mid + 1; ans = mid;
}
if (ans == -1) return -1;
int cur = jump2(b, ans);
//cout << cur << '\n';
l = 0, r = n; int ans2 = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int x = jump(cur, mid);
//cout << mid << " | " << x << '\n';
if (x == 0) {
r = mid - 1; continue;
}
// cout << mid << " n\n";
// cout << nxt[x] << " " << c << " " << mid << '\n';
if (nxt[x] && nxt[x] < c) {
l = mid + 1; ans2 = mid; continue;
}
r = mid - 1;
}
// cout << ans2 << '\n';
if (true) {
int u = jump(cur, ans2 + 1);
if (u) {
if (nxt[u] && nxt[u] <= d) ans2++;
}
}
int cur2 = jump(cur, ans2);
//cout << cur2 << '\n';
// cout << cur2 << '\n'; //cout << ans2 << '\n';
l = 0, r = n; int ans3 = -1;
// cout << nxt[cur2] << '\n';
// cout << nxt[nxt[cur2]] << '\n';
// cout << nxt[nxt[nxt[cur2]]] << '\n';
/*for (int i = 0; i <= 20; i++) {
cout << i << ": " << jump3(cur2, i) << '\n';
}*/
while (l <= r) {
int mid = (l + r) >> 1;
int x = jump3(cur2, mid);
//cout << c << " " << x << " | " << mid << '\n';
if (!x || x >= c) {
r = mid - 1; ans3 = mid;
} else {
l = mid + 1;
}
}
//cout << ans3 << '\n';
if (ans3 == -1) return -1;
int cur3 = jump3(cur2, ans3);
if (!cur3) return -1;
//cout << cur3 << '\n';
if (cur3 > d) return -1;
return ans2 + ans3;
}
