#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5;
int toright[nmax][18], toleft[nmax][18];
int extreme[nmax][18];
int H[nmax];
int N;
void init(int N_, std::vector<int> H_) {
N = N_;
H_.emplace_back(1e9 + 5);
for(int i = 0; i <= N; i++) H[i] = H_[i];
vector<int> st;
st.emplace_back(N);
for(int i = 0; i < N; i++) {
while(H[st.back()] < H[i]) st.pop_back();
toleft[i][0] = st.back();
st.emplace_back(i);
}
toleft[N][0] = N;
for(int step = 1; step < 18; step++) for(int i = 0; i <= N; i++) toleft[i][step] = toleft[toleft[i][step - 1]][step - 1];
st.clear();
st.emplace_back(N);
for(int i = N - 1; i >= 0; i--) {
while(H[st.back()] < H[i]) st.pop_back();
toright[i][0] = st.back();
st.emplace_back(i);
}
toright[N][0] = N;
for(int step = 1; step < 18; step++) for(int i = 0; i <= N; i++) toright[i][step] = toright[toright[i][step - 1]][step - 1];
for(int i = 0; i < N; i++) {
if(toleft[i][0] == N) extreme[i][0] = toright[i][0];
else if(toright[i][0] == N) extreme[i][0] = toleft[i][0];
else extreme[i][0] = (H[toleft[i][0]] > H[toright[i][0]]? toleft[i][0] : toright[i][0]);
}
extreme[N][0] = N;
for(int step = 1; step < 18; step++) for(int i = 0; i <= N; i++) extreme[i][step] = extreme[extreme[i][step - 1]][step - 1];
}
int maxrange(int l, int r) {
for(int i = 17; i >= 0; i--)
if(toright[l][i] <= r) l = toright[l][i];
return l;
}
int leftist(int B, int C, int D) {
if(B == N) return -1;
int cnt = 0;
for(int i = 17; i >= 0; i--) {
int cand = toright[B][i];
if(cand >= C) continue;
B = cand;
cnt += (1 << i);
}
if(toright[B][0] > D) return -1;
return cnt + 1;
}
int minimum_jumps(int A, int B, int C, int D) {
vector<int> arriv(N + 1, N + 1);
queue<int> que;
for(int i = A; i <= B; i++) {
arriv[i] = 0;
que.emplace(i);
}
while(!que.empty()) {
int node = que.front();
que.pop();
if(node == N) continue;
if(C <= node && node <= D) return arriv[node];
int l = toleft[node][0], r = toright[node][0];
if(arriv[l] == N + 1) arriv[l] = arriv[node] + 1, que.emplace(l);
if(arriv[r] == N + 1) arriv[r] = arriv[node] + 1, que.emplace(r);
}
return -1;
}
/**
Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/
