#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> H;
int lg;
vector<vector<int>> out;
vector<vector<int>> mn,mx,fr,bk,rmq;
void init(int N2, std::vector<int> H2){
N=N2;
H=H2;
H.push_back(1e9);
lg = log2(N) + 1;
mx.resize(lg);
mn.resize(lg);
fr.resize(lg);
bk.resize(lg);
rmq.resize(lg);
for (int i=0;i<lg;i++){
mx[i].resize(N+1);
mn[i].resize(N+1);
fr[i].resize(N+1);
bk[i].resize(N+1);
rmq[i].resize(N+1);
fill(fr[i].begin(),fr[i].end(),N);
fill(bk[i].begin(),bk[i].end(),N);
}
stack<int> s;
out.resize(N);
for (int i=0;i<N;i++){
while (s.size() && H[s.top()] < H[i]){
out[s.top()].push_back(i);
fr[0][s.top()] = (i);
s.pop();
}
s.push(i);
}
while (s.size()) s.pop();
for (int i=N-1;i>=0;i--){
while (s.size() && H[s.top()] < H[i]){
out[s.top()].push_back(i);
bk[0][s.top()] = i;
s.pop();
}
s.push(i);
}
for (int i=0;i<N;i++){
if (out[i].size() == 1){
mx[0][i] = mn[0][i] = out[i][0];
} else if (out[i].size() == 2){
int a = out[i][0], b = out[i][1];
if (H[a] > H[b]) swap(a,b);
mn[0][i] = a;
mx[0][i] = b;
} else {
mn[0][i] = mx[0][i] = N;
}
}
iota(rmq[0].begin(),rmq[0].end(),0);
mx[0][N] = mn[0][N] = N;
for (int i=1;i<lg;i++){
for (int j=0;j<=N;j++){
mx[i][j] = mx[i-1][mx[i-1][j]];
mn[i][j] = mn[i-1][mn[i-1][j]];
fr[i][j] = fr[i-1][fr[i-1][j]];
bk[i][j] = bk[i-1][bk[i-1][j]];
int a = rmq[i-1][j];
int b = rmq[i-1][min(N,j + (1<<(i-1)))];
if (H[a] > H[b]){
rmq[i][j] = a;
} else {
rmq[i][j] = b;
}
}
}
}
int get_max(int l, int r){
int g = log2(r-l+1);
int x = rmq[g][l];
int y = rmq[g][r - (1<<g) + 1];
if (H[x] > H[y]) return x;
return y;
}
int minjumps(int A, int C){
int ans = 0;
for (int k=lg-1;(A!=C) && (k>=0);k--){
if (H[mx[k][A]] <= H[C]){
A = mx[k][A];
ans += (1 << k);
}
}
for (int k=lg-1;(A!=C) && (k>=0);k--){
if (H[mn[k][A]] <= H[C]){
A = mn[k][A];
ans += (1 << k);
}
}
if (A == C){
return ans;
}
return -1;
}
int minjumps(int A, int B, int C){
if (H[B] > H[C]) return -1;
int l = A, r = B;
int pref = B;
while (l < r){
int m = (l+r)/2;
if (H[get_max(m+1,r)] < H[C]){
pref = m+1;
r = m;
} else {
l = m+1;
}
}
if (l == r){
if (H[l]< H[C]) pref = l;
}
A = get_max(pref, B);
return minjumps(A,C);
}
int minimum_jumps(int A, int B, int C, int D) {
if (C-B == 1){
if (fr[0][B] >= C && fr[0][B] <= D) return 1;
else return -1;
} else {
int mid = get_max(B+1,C-1);
int x = B;
int ans = 1e9;
if (H[x] < H[mid]){
for (int k=lg-1;k>=0;k--){
if (bk[k][x] >= A){
if (H[bk[k][x]] < H[mid]){
x = bk[k][x];
}
}
}
x = bk[0][x];
if (x >= A && x <= B){
if (fr[0][x] >= C && fr[0][x] <= D) ans=1;
} else {
if (fr[0][x] >= C && fr[0][x] <= D) ans = 2;
}
} else {
if (fr[0][x] >= C && fr[0][x] <= D ) return 1;
}
int y = minjumps(A,B,mid);
if (y != -1) if (fr[0][mid] >= C && fr[0][mid] <= D) ans = min(ans, y+1);
if (ans == 1e9) return -1;
else return ans;
}
}
