#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for (auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 2e9;
const ll BASE = 137;
int n, A, B, C, D;
int a[N];
int spt[N][25], spt2[N][25];
pair<int,int> mx[N][25];
pair<int,int> nxt[N];
pair<int,int> get (int L, int R) {
if (L > R) return {-INF, 0};
int K = 31 - __builtin_clz(R - L + 1);
return max(mx[L][K], mx[R - (1 << K) + 1][K]);
}
int minimum_jumps (int A, int B, int C, int D) {
++A, ++B, ++C, ++ D;
int X = get(C, D).fs;
int bound; {
int lf = A, rt = B;
while (lf < rt) {
int mid = lf + rt >> 1;
if (get(mid, B).fs < X) rt = mid;
else lf = mid + 1;
}
bound = lf;
}
if (get(bound, B).fs > X) {
return -1;
}
if (get(B + 1, C - 1).fs > X) {
return -1;
}
int pos = get(bound, B).se;
ll res = 0;
reb (i, 17, 0) {
if (a[spt2[pos][i]] <= get(B + 1, C - 1).fs) {
pos = spt2[pos][i];
res += (1 << i);
}
}
if (a[spt2[pos][0]] <= X && a[pos] < get(B + 1, C - 1).fs) {
++res;
pos = spt2[pos][0];
if (pos < C) ++res;
return res;
}
reb (i, 17, 0) {
if (spt[pos][i] < C) {
pos = spt[pos][i];
res += (1 << i);
}
}
++res;
return res;
}
//void solution() {
void init (int _n, vector<int> _a) {
// cin >> n;
// cin >> A >> B >> C >> D;
// rep (i, 1, n) cin >> a[i];
n = _n;
rep (i, 1, n) a[i] = _a[i - 1];
stack<pair<int,int>> st;
rep (i, 1, n) {
while (!st.empty() && st.top().se < a[i]) st.pop();
if (st.empty()) nxt[i].fs = i;
else nxt[i].fs = st.top().fs;
st.push({i, a[i]});
}
stack<pair<int,int>> ().swap(st);
reb (i, n, 1) {
while (!st.empty() && st.top().se < a[i]) st.pop();
if (st.empty()) nxt[i].se = i;
else nxt[i].se = st.top().fs;
st.push({i, a[i]});
}
rep (i, 1, n) {
if (a[nxt[i].fs] > a[nxt[i].se]) swap (nxt[i].fs, nxt[i].se);
spt[i][0] = max(nxt[i].fs, nxt[i].se);
spt2[i][0] = nxt[i].se;
}
rep (j, 1, 17)
rep (i, 1, n) spt[i][j] = spt[spt[i][j - 1]][j - 1], spt2[i][j] = spt2[spt2[i][j - 1]][j - 1];
rep (i, 1, n) mx[i][0] = {a[i], i};
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
}
//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
//// file("c");
// ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
no bug challenge +2
7
3 2 1 6 4 5 7
*/
