#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int best[200005][25], rightt[200005][25], h[200005], n, tallest[2000000], L[200005];
void update(int id, int l, int r, int pos, int val){
if(h[val] > h[tallest[id]]){
tallest[id] = val;
}
if(l == r){
return;
}
int m = l + r >> 1;
if(m >= pos){
update(id * 2, l, m, pos, val);
}
else update(id * 2 + 1, m + 1, r, pos, val);
}
int query(int id, int l, int r, int lef, int rig){
if(lef > rig) return 200004;
if(r < lef || rig < l) return 200004;
if(lef <= l && r <= rig) return tallest[id];
int m = l + r >> 1;
int lll = query(id * 2, l, m, lef, rig);
int rrr = query(id * 2 + 1, m + 1, r, lef, rig);
return (h[lll] > h[rrr] ? lll : rrr);
}
void init(int N, vector<int> H){
n = N;
for(int i = 1; i <= n; i++){
h[i] = H[i - 1];
update(1, 1, n, i, i);
}
stack<int> s, t;
h[n + 1] = 1e9;
s.push(n + 1);
for(int i = n; i >= 1; i--){
while(h[s.top()] < h[i]){
s.pop();
}
rightt[i][0] = s.top();
s.push(i);
}
t.push(0);
h[0] = 1e9;
for(int i = 1; i <= n; i++){
while(h[t.top()] < h[i]){
t.pop();
}
L[i] = t.top();
t.push(i);
}
for(int i = 1; i <= n; i++){
if(h[L[i]] < 1e9 && h[rightt[i][0]] < 1e9){
best[i][0] = (h[L[i]] > h[rightt[i][0]] ? L[i] : rightt[i][0]);
}
else{
if(h[L[i]] < 1e9){
best[i][0] = L[i];
}
else{
if(h[rightt[i][0]] < 1e9){
best[i][0] = rightt[i][0];
}
else best[i][0] = 0;
}
}
}
rightt[n + 1][0] = n + 1;
for(int j = 1; j <= 20; j++){
for(int i = 0; i <= n + 1; i++){
rightt[i][j] = rightt[rightt[i][j - 1]][j - 1];
best[i][j] = best[best[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D){
A++, B++, C++, D++;
int x = query(1, 1, n, B + 1, C - 1);
int y = query(1, 1, n, C, D);
// cout << x << ' ' << y << '\n';
if(h[x] > h[y]) return -1;
if(h[B] > h[y]) return -1;
int z = query(1, 1, n, A, B);
if(h[z] > h[y]){
int pos = query(1, 1, n, z + 1, B);
int ans = 0;
for(int i = 20; i >= 0; i--){
if(C > rightt[pos][i]){
ans += (1 << i);
pos = rightt[pos][i];
}
}
return ans + 1;
}
else{
int ans = 0;
int pos = z;
// cout << pos << ' ' << x << '\n';
for(int i = 20; i >= 0; i--){
if(h[best[pos][i]] < h[x]){
pos = best[pos][i];
ans += (1 << i);
}
}
// cout << best[pos][0] << ' ' << ans << '\n';
if(h[best[pos][0]] < h[y]){
if(best[pos][0] >= C && best[pos][0] <= D) ans ++;
else ans += 2;
}
else{
for(int i = 20; i >= 0; i--){
// cout << pos << '\n';
if(C > rightt[pos][i]){
ans += (1 << i);
pos = rightt[pos][i];
}
}
ans++;
}
return ans;
}
}
