#include<bits/stdc++.h>
#define ll long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
struct TABLE{
int n;
int g;
vector< vector< int > > dp;
TABLE(){}
TABLE(vector< int > &v){
n = SZ(v);
g = __lg(n) + 1;
dp.resize(g, vector< int >(n));
for(int i = 0; i < n; ++i){
dp[0][i] = v[i];
}
for(int j = 1; j < g; ++j){
for(int i = 0; i + (1 << j) - 1 < n; ++i){
dp[j][i] = max(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r){
int lg = __lg(r - l + 1);
return max(dp[lg][l], dp[lg][r - (1 << lg) + 1]);
}
};
TABLE RMQ;
vector< vector< int > > big, small;
vector< int > h;
void init(int n, vector<int> H) {
h = H;
vector< int > l(n, n), r(n, n);
h.push_back(n + 1);
{
vector< int > stk;
for(int i = 0; i < n; ++i){
while(!stk.empty() && h[stk.back()] < h[i]){
r[stk.back()] = i;
stk.pop_back();
}
l[i] = stk.empty() ? n : stk.back();
stk.push_back(i);
}
}
RMQ = TABLE(h);
big.resize(20, vector< int >(n + 1));
small.resize(20, vector< int >(n + 1));
for(int i = 0; i < n; ++i){
if(h[l[i]] > h[r[i]]) big[0][i] = l[i], small[0][i] = r[i];
else small[0][i] = l[i], big[0][i] = r[i];
}
big[0][n] = small[0][n] = n;
for(int i = 1; i < 20; ++i){
for(int j = 0; j <= n; ++j){
big[i][j] = big[i - 1][big[i - 1][j]];
small[i][j] = small[i - 1][small[i - 1][j]];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
int l = a, r = b, ans = b;
while(l <= r){
int mid = (l + r) >> 1;
if(RMQ.query(mid, r) <= h[c]){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
int now = ans;
int cnt = 0;
for(int i = 19; i >= 0; --i){
if(h[big[i][now]] <= h[c]) now = big[i][now], cnt += (1 << i);
}
for(int i = 19; i >= 0; --i){
if(h[small[i][now]] <= h[c]) now = small[i][now], cnt += (1 << i);
}
if(now != c) return -1;
return cnt;
}
