#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a,b,c,d) for(int a = b;a <= c; a += d)
#define repl(a,b,c,d) for(int a = b; a >= c; a -= d)
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
const int LG = 19;
const int N = 2e5 + 5;
int lg[N];
int upb[N][LG];
int ups[N][LG];
int nxt[N];
int lst[N];
int tv[N];
int n;
void prec() {
lg[1] = 0;
rep(i, 2, N - 1, 1)
lg[i] = lg[i >> 1] + 1;
}
struct sparse{
V<int> arr;
V<V<int>> mn;
V<V<int>> mx;
int n, l;
int comparemn(int a, int b) {
if (arr[a] <= arr[b]) {
return a;
}
return b;
}
int comparemx(int a, int b) {
if (arr[a] >= arr[b]) {
return a;
}
return b;
}
void init(int nn, V<int> a) {
n = nn;
l = lg[n] + 1;
arr = a;
mn.resize(n + 1, V<int>(l + 1));
mx.resize(n + 1, V<int>(l + 1));
rep(i, 1, n, 1) {
mn[i][0] = i;
mx[i][0] = i;
}
rep(j, 1, l, 1) {
rep(i, 1, n, 1) {
mn[i][j] = comparemn(mx[i][j - 1], mx[min(i + (1 << (j - 1)), n)][j - 1]);
mx[i][j] = comparemx(mx[i][j - 1], mx[min(i + (1 << (j - 1)), n)][j - 1]);
}
}
}
int range_min(int l, int r) {
int d = r - l + 1;
int log = lg[d];
return comparemn(mn[l][log], mn[r - (1 << log) + 1][log]);
}
int range_max(int l, int r) {
int d = r - l + 1;
int log = lg[d];
return comparemx(mx[l][log], mx[r - (1 << log) + 1][log]);
}
} rmq;
void init(int nn, vector<int> H) {
n = nn;
prec();
rep(i, 1, n, 1) {
tv[i] = H[i - 1];
}
V<int> a(n + 1);
rep(i, 0, n, 1) {
a[i] = tv[i];
}
rmq.init(n, a);
stack<int> st;
st.push(1);
rep(i, 2, n, 1) {
while (!st.empty() && a[st.top()] < a[i]) {
nxt[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
nxt[st.top()] = n + 1;
st.pop();
}
st.push(n);
repl(i, n - 1, 1, 1) {
while (!st.empty() && a[st.top()] < a[i]) {
lst[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
lst[st.top()] = 0;
st.pop();
}
auto valid = [&] (int x) {
return (1 <= x && x <= n);
};
auto compareb = [&](int i) {
int a = nxt[i];
int b = lst[i];
int c = i;
int cur = -1;
if (valid(a))
cur = a;
if (valid(b)) {
if (cur == -1 || tv[cur] < tv[b]) {
cur = b;
}
}
if (valid(c)) {
if (cur == -1 || tv[cur] < tv[c]) {
cur = c;
}
}
return cur;
};
auto compares = [&](int i) {
int a = nxt[i];
int b = lst[i];
int c = i;
int cur = -1;
if (valid(a))
cur = a;
if (valid(b)) {
if (cur == -1 || tv[cur] > tv[b]) {
cur = b;
}
}
if (cur != -1) {
return cur;
}
if (valid(c)) {
if (cur == -1 || tv[cur] > tv[c]) {
cur = c;
}
}
return cur;
};
rep(i, 1, n, 1) {
upb[i][0] = compareb(i);
ups[i][0] = compares(i);
}
int l = lg[n] + 1;
rep (j, 1, l, 1) {
rep(i, 1, n, 1) {
upb[i][j] = upb[upb[i][j - 1]][j - 1];
ups[i][j] = ups[ups[i][j - 1]][j - 1];
}
}
}
int ds(int A, int C) {
if (tv[rmq.range_max(A, C - 1)] >= tv[C]) {
return 1e8;
}
int l = lg[n] + 1;
int cur = 0;
repl(i, l, 0, 1) {
if (tv[upb[A][i]] < tv[C]) {
A = upb[A][i];
cur += (1 << i);
}
}
if (upb[A][0] == C) {
return cur + 1;
}
repl(i, l, 0, 1) {
if (tv[ups[A][i]] < tv[C]) {
A = ups[A][i];
cur += (1 << i);
}
}
return cur + 1;
}
int sl(int A, int B, int C) {
int ans = 1e8;
int x = lst[C];
if (x >= B) {
return 1e8;
}
A = rmq.range_max(max(A, x + 1), B);
ans = ds(A, C);
return ans;
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 1e8;
++A; ++B; ++C; ++D;
rep(i, C, D, 1) {
ans = min(ans, sl(A, B, C));
}
if (ans == 1e8)
return -1;
return ans;
}
