#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int LG = 19, maxn = 2e5 + 5;
pair<int, int> maxjump[LG][maxn], minjump[LG][maxn], spmax[LG][maxn];
pair<int, int> get(int l, int r){
int k = __lg(r - l + 1);
return max(spmax[k][l], spmax[k][r - (1 << k) + 1]);
}
int n, q;
vector<int> h, l, r;
void init(int N, vector<int> H){
n = N;
h.assign(n + 1, 0);
l.assign(n + 1, -1);
r.assign(n + 1, -1);
for(int i = 1; i <= n; i++) h[i] = H[i - 1];
{
vector<int> st;
for(int i = 1; i <= n; i++){
while(st.size() && h[st.back()] <= h[i]) st.pop_back();
if(st.size()) l[i] = st.back();
st.push_back(i);
}
}
{
vector<int> st;
for(int i = n; i >= 1; i--){
while(!st.empty() && h[st.back()] <= h[i]) st.pop_back();
if(!st.empty()) r[i] = st.back();
st.push_back(i);
}
}
for(int i = 1; i <= n; i++){
priority_queue<pair<int, int>> pq;
if(l[i] != -1) pq.push({h[l[i]], l[i]});
if(r[i] != -1) pq.push({h[r[i]], r[i]});
if(pq.size()){
maxjump[0][i] = pq.top();
pq.pop();
}if(pq.size()){
minjump[0][i] = pq.top();
pq.pop();
}
spmax[0][i] = {h[i], i};
}
for(int j = 1; j < LG; j++){
for(int i = 1; i <= n; i++){
maxjump[j][i] = maxjump[j - 1][ maxjump[j - 1][i].second ];
minjump[j][i] = minjump[j - 1][ minjump[j - 1][i].second ];
}
for(int i = 1; i + (1 << j) - 1 <= n; i++) spmax[j][i] = max(spmax[j - 1][i], spmax[j - 1][i + (1 << (j - 1))]);
}
}
int minimum_jumps(int a, int b, int c, int d){
a++; b++; c++; d++;
if(c == b + 1){
if(h[b] < get(c, d).first) return 1;
else return -1;
}
int r = b, peak = get(c, d).second, block = get(b + 1, c - 1).second, rpos = l[block];
if(h[block] >= h[peak]) return -1;
for(int i = LG - 1; i >= 0; i--){
if(r - (1 << i) >= a && get(r - (1 << i), b).first < h[block]) r -= (1 << i);
}
int cur = get(r, b).second, res = 0;
for(int i = LG - 1; i >= 0; i--){
if(maxjump[i][cur].second && maxjump[i][cur].first <= h[block]){
cur = maxjump[i][cur].second;
res += (1 << i);
}
}
for(int i = LG - 1; i >= 0; i--){
if(minjump[i][cur].second && minjump[i][cur].first <= h[block]){
cur = minjump[i][cur].second;
res += (1 << i);
}
}
int kq = 1e9;
if(cur == block) kq = min(kq, res);
if(rpos != -1 && h[rpos] < h[peak]){
int ans = 0;
if(a <= rpos && rpos <= b) cur = rpos;
else{
cur = get(a, b).second;
for(int i = LG - 1; i >= 0; i--){
if(maxjump[i][cur].second && maxjump[i][cur].first <= h[rpos]){
cur = maxjump[i][cur].second;
ans += (1 << i);
}
}
for(int i = LG - 1; i >= 0; i--){
if(minjump[i][cur].second && minjump[i][cur].first <= h[rpos]){
cur = minjump[i][cur].second;
ans += (1 << i);
}
}
}
if(cur == rpos) kq = min(kq, ans);
}
if(kq == 1e9) return -1;
else return kq + 1;
}
