#include <bits/stdc++.h>
using namespace std;
void chmax(int& a, int b){ if(a < b) a = b; }
int N;
vector<int> H, RMQ, idx;
vector<vector<int>> low, high;
int get(int l, int r){
int ans = 0;
for(l += N, r += N; l < r; l >>= 1, r >>= 1){
if(l & 1) chmax(ans, RMQ[l++]);
if(r & 1) chmax(ans, RMQ[--r]);
}
return ans;
}
int get_idx(int l, int r){
int ans = N;
for(l += N, r += N; l < r; l >>= 1, r >>= 1){
if(l & 1){
if(H[ans] < H[idx[l]]) ans = idx[l];
l++;
}
if(r & 1){
r--;
if(H[ans] < H[idx[r]]) ans = idx[r];
}
}
return ans;
}
void init(int N, vector<int> H) {
::N = N;
::H = H;
RMQ.resize(N);
RMQ.insert(RMQ.end(), H.begin(), H.end());
for(int i = N; --i; ) RMQ[i] = max(RMQ[i << 1], RMQ[i << 1 | 1]);
idx.resize(N * 2);
for(int i = 0; i < N; i++) idx[N + i] = i;
for(int i = N; --i; ) idx[i] = H[idx[i << 1]] > H[idx[i << 1 | 1]] ? idx[i << 1] : idx[i << 1 | 1];
::H.push_back(0);
set<int> idx;
for(int i = 0; i < N; i++) idx.insert(idx.end(), i);
vector<int> h(N);
iota(h.begin(), h.end(), 0);
sort(h.begin(), h.end(), [&](int x, int y){ return H[x] < H[y]; });
low.assign(18, vector<int>(N, -1));
high.assign(18, vector<int>(N, -1));
for(int i : h){
auto p = idx.find(i);
if(p != idx.begin()) high[0][i] = *prev(p);
p = idx.erase(p);
if(p != idx.end()){
if(high[0][i] == -1) high[0][i] = *p;
else{
low[0][i] = *p;
if(H[low[0][i]] > H[high[0][i]]) swap(low[0][i], high[0][i]);
}
}
}
for(int i = 0; i < 17; i++) for(int j = 0; j < N; j++){
if(low[i][j] != -1) low[i + 1][j] = low[i][low[i][j]];
if(high[i][j] != -1) high[i + 1][j] = high[i][high[i][j]];
}
}
int minimum_jumps(int A, int B, int C, int D) {
const int X = get(B, C), Y = get(C, D + 1);
if(X >= Y) return -1;
if(get(A, B + 1) >= Y){
int ok = B, ng = A;
while(ok - ng > 1){
const int cen = (ok + ng) / 2;
(get(cen, B + 1) >= Y ? ng : ok) = cen;
}
A = ok;
}
if(get(A, B + 1) >= X) return 1;
int ans = 2, at = get_idx(A, B + 1);
for(int i = 18; i--; ) if(high[i][at] != -1 && H[high[i][at]] < X){
ans += 1 << i;
at = high[i][at];
}
if(high[0][at] != -1 && H[high[0][at]] < Y) return ans;
for(int i = 18; i--; ) if(low[i][at] != -1 && H[low[i][at]] < X){
ans += 1 << i;
at = low[i][at];
}
return ans;
}
