#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
int n;
int h[200005];
int leftJump[200005];
int rightJump[200005];
int weakDepth[200005];
int strongDepth[200005];
int weakJump[200005][20];
int strongJump[200005][20];
void init(int N, vector<int> heights) {
// hello little space complexity
memset(leftJump, -1, sizeof(leftJump));
memset(rightJump, -1, sizeof(rightJump));
memset(weakJump, -1, sizeof(weakJump));
memset(strongJump, -1, sizeof(strongJump));
memset(weakDepth, -1, sizeof(weakDepth));
memset(strongDepth, -1, sizeof(strongDepth));
n = N;
for(int i = 0; i < n; i++) h[i] = heights[i];
// monotonic stack ftw
stack<pair<int, int>> maxStack;
maxStack.push(make_pair(n+1, -1));
for(int i = 0; i < n; i++) {
while(maxStack.top().first <= h[i]) maxStack.pop();
if(maxStack.top().second > -1) leftJump[i] = maxStack.top().second;
maxStack.push(make_pair(h[i], i));
}
while(!maxStack.empty()) maxStack.pop();
maxStack.push(make_pair(n+1, n));
for(int i = n-1; i >= 0; i--) {
while(maxStack.top().first <= h[i]) maxStack.pop();
if(maxStack.top().second < n) rightJump[i] = maxStack.top().second;
maxStack.push(make_pair(h[i], i));
}
for(int i = 0; i < n; i++) {
if(leftJump[i] == -1 && rightJump[i] == -1) continue;
else if(leftJump[i] != -1 && rightJump[i] != -1) {
if(h[leftJump[i]] < h[rightJump[i]]) {
weakJump[i][0] = leftJump[i];
} else {
weakJump[i][0] = rightJump[i];
}
}
if(h[leftJump[i]] < h[rightJump[i]]) {
strongJump[i][0] = rightJump[i];
} else strongJump[i][0] = leftJump[i];
}
// for(int i = 0; i < n; i++) {
// cout << i << ' ' << weakJump[i][0] << ' ' << strongJump[i][0] << '\n';
// }
auto dfsWeak = [&](auto &&dfsWeak, int v) -> void {
if(weakDepth[v] != -1) return;
if(weakJump[v][0] != -1) {
dfsWeak(dfsWeak, weakJump[v][0]);
weakDepth[v] = max(weakDepth[v], weakDepth[weakJump[v][0]] + 1);
}
weakDepth[v] = max(weakDepth[v], 0);
for(int i = 1; 1ll<<i <= weakDepth[v]; i++) {
weakJump[v][i] = weakJump[weakJump[v][i-1]][i-1];
// printf("weak %d %d goes to %d\n", v, i, weakJump[v][i]);
}
};
auto dfsStrong = [&](auto &&dfsStrong, int v) -> void {
if(strongDepth[v] != -1) return;
if(strongJump[v][0] != -1) {
dfsStrong(dfsStrong, strongJump[v][0]);
strongDepth[v] = max(strongDepth[v], strongDepth[strongJump[v][0]] + 1);
}
strongDepth[v] = max(strongDepth[v], 0);
for(int i = 1; 1ll<<i <= strongDepth[v]; i++) {
strongJump[v][i] = strongJump[strongJump[v][i-1]][i-1];
// printf("strong %d %d goes to %d\n", v, i, strongJump[v][i]);
}
};
for(int i = 0; i < n; i++) {
dfsWeak(dfsWeak, i);
if(strongJump[i][0] != -1) dfsStrong(dfsStrong, i);
}
}
int weakJumps(int v, int x) {
int res = v;
for(int i = 19; i >= 0; i--) {
if(weakJump[res][i] != -1) if(x & (1ll<<i)) {
res = weakJump[res][i];
x -= (1ll<<i);
}
}
return res;
}
int minimum_jumps(int A, int B, int C, int D) {
assert(A == B);
assert(C == D);
int l = -1, r = weakDepth[A]+1;
int x = -1;
while(l+1 < r) {
int m = (l+r)/2;
// cout << "checking " << m << '\n';
int s = weakJumps(A, m);
// cout << "from " << A << " to " << s << '\n';
int js = 0;
for(int i = 19; i >= 0; i--) {
if(strongJump[s][i] != -1) {
// cout << "try to jump by " << (1ll<<i) << '\n';
if(h[strongJump[s][i]] <= h[C]) {
// cout << "jumped by " << (1ll<<i) << '\n';
s = strongJump[s][i];
js += 1ll<<i;
}
}
}
if(s == C) {
// cout << "# of jumps: " << js+m << '\n';
x = js + m;
r = m;
}
else l = m;
}
return x;
}
