#include<jumps.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22;
struct Node{
Node *L, *R;
int val = 0;
Node(int v){
L = R = nullptr;
val = v;
}
Node(Node *l, Node *r){
L = l, R = r;
val = L->val + R->val;
}
};
Node* build(int l, int r){
if(l == r){
return new Node(0);
}
int m = l+r>>1;
return new Node(build(l, m), build(m+1, r));
}
Node* update(Node* v, int l, int r, int p){
if(l == r){
return new Node(1);
}
int m = l+r>>1;
if(p <= m){
return new Node(update(v->L, l, m, p), v->R);
}
return new Node(v->L, update(v->R, m+1, r, p));
}
int get(Node* vl, Node *vr, int l, int r, int lim){
if(l == r)
return (l < lim) > 0 ? l : -1;
int m = l+r>>1;
if(vr->R->val - vl->R->val > 0)
return get(vl->R, vr->R, m+1, r, lim);
return get(vl->L, vr->L, l, m, lim);
}
int n, L[N], R[N], up[N][K][2];
vector<int> H;
vector<Node*> roots;
void init(int _n, vector<int> h){
n = _n;
H = h;
H.pb(MOD);
deque<int> q;
L[0] = n;
q.pb(0);
for(int i = 1; i < n; ++i){
while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
if(!q.empty()) L[i] = q.back();
else L[i] = n;
q.pb(i);
}
q.clear();
R[n-1] = n;
q.pb(n-1);
for(int i = n-2; i >= 0; --i){
while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
if(!q.empty()) R[i] = q.back();
else R[i] = n;
q.pb(i);
}
up[n][0][0] = n;
up[n][0][1] = n;
for(int i = 0; i < n; ++i){
if(H[L[i]] > H[R[i]]){
up[i][0][0] = L[i];
up[i][0][1] = R[i];
}else{
up[i][0][1] = L[i];
up[i][0][0] = R[i];
}
}
for(int j = 1; j < K; ++j){
for(int i = 0; i <= n; ++i){
up[i][j][0] = up[up[i][j - 1][0]][j - 1][0];
up[i][j][1] = up[up[i][j - 1][1]][j - 1][1];
}
}
roots.pb(build(1, n));
for(int i = 1; i <= n; ++i){
roots.pb(update(roots.back(), 1, n, H[i - 1]));
}
}
int minimum_jumps(int A, int B, int C, int D){
int v, ans = 0;
v = get(roots[B + 1], roots[A], 1, n, H[C]) - 1;
if(v == -2) return -1;
for(int j = K - 1; j >= 0; --j){
if(H[up[v][j][0]] <= H[C]){
ans += (1<<j);
v = up[v][j][0];
}
}
for(int j = K - 1; j >= 0; --j){
if(H[up[v][j][1]] <= H[C]){
ans += (1<<j);
v = up[v][j][1];
}
}
if(v == C) return ans;
return -1;
}
