#include "jumps.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int N = 200002;
const int inf = 1 << 20;
int mx[N][20], h[N], pl[N], pr[N], p[N];
int bl[N][20], bl_r[N][20];
int n;
void mx_prec(){
for(int i = 1; i <= n; i++){
mx[i][0] = h[i];
}
for(int j = 1; j < 20; j++){
for(int i = 1; i <= n + 1 - (1 << j); i++){
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
}
}
}
void bl_prec(){
bl[0][0] = 0, bl[n + 1][0] = n + 1;
for(int i = 1; i <= n; i++){
bl[i][0] = p[i];
}
for(int j = 1; j < 20; j++){
for(int i = 0; i <= n + 1; i++){
bl[i][j] = bl[bl[i][j - 1]][j - 1];
}
}
bl_r[0][0] = 0, bl_r[n + 1][0] = n + 1;
for(int i = 1; i <= n; i++){
bl_r[i][0] = pr[i];
}
for(int j = 1; j < 20; j++){
for(int i = 0; i <= n + 1; i++){
bl_r[i][j] = bl_r[bl_r[i][j - 1]][j - 1];
}
}
}
int mx_qry(int l, int r){
if(l <= 0 || r >= n + 1 || l > r + 1) return inf;
if(l == r + 1) return 0;
int d = __lg(r - l + 1);
return max(mx[l][d], mx[r - (1 << d) + 1][d]);
}
void init(int N, std::vector<int> H) {
::n = N;
for(int i = 1; i <= N; i++){
h[i] = H[i - 1];
}
h[0] = h[n + 1] = inf;
pl[0] = 0, pr[0] = 0, pl[n + 1] = n + 1, pr[n + 1] = n + 1;
vector<pii> L {{inf, 0}};
for(int i = 1; i <= n; i++){
while(L.back().fi < h[i]) L.pop_back();
pl[i] = L.back().se;
L.push_back({h[i], i});
}
vector<pii> R {{inf, n + 1}};
for(int i = n; i >= 1; i--){
while(R.back().fi < h[i]) R.pop_back();
pr[i] = R.back().se;
R.push_back({h[i], i});
}
p[0] = 0, p[n + 1] = n + 1;
for(int i = 1; i <= n; i++){
p[i] = h[pl[i]] < h[pr[i]] ? pr[i] : pl[i];
}
mx_prec();
bl_prec();
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
if(mx_qry(B + 1, C - 1) > mx_qry(C, D)) return -1;
// cerr << "ST1";
int mx_CD = mx_qry(C, D);
int mx_gap = mx_qry(B + 1, C - 1);
int mx_val_AB = inf, mx_idx_AB = -1;
{
int l = 0, r = B - A + 1;
while(l != r){
int m = (l + r + 1) / 2;
if(mx_qry(B - m + 1, B) < mx_qry(C, D)){
l = m;
}else{
r = m - 1;
}
}
mx_val_AB = mx_qry(B - l + 1, B);
}
if(mx_val_AB == inf) return -1;
// cerr << "ST2";
{
int l = 0, r = B - A;
while(l != r){
int m = (l + r + 1) / 2;
if(mx_qry(B - m, B) < mx_val_AB){
l = m;
}else{
r = m - 1;
}
}
mx_idx_AB = B - l;
}
if(mx_val_AB == inf) return -1;
// cerr << "ST3";
int ST = mx_idx_AB;
int ans = 0;
{
int steps = 0;
for(int j = 19; j >= 0; j--){
if(h[bl[ST][j]] < mx_gap) steps += (1 << j), ST = bl[ST][j];
}
if(h[ST] < mx_gap) steps++, ST = bl[ST][0];
ans += steps;
}
// cerr << "ST4";
// cout << ST << ' ' << ans << ' ' << C << ' ' << D << endl;
{
if(ST < C) ST = pr[ST], ans++;
if(C <= ST && ST <= D) return ans;
else return -1;
}
}
