#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, mod = 1e9 + 7;
const ll inf = 9e18;
int n, q, st[N][20], jump[N][20], lst[N], rst[N], a[N];
int get(int l, int r) {
int lgg = __lg(r-l+1);
int id1 = st[l][lgg];
int id2 = st[r - (1 << lgg) + 1][lgg];
return (a[id1] > a[id2]) ? id1 : id2;
}
void init(int n, vector <int> H) {
for (int i = 1; i <= n; ++i) a[i] = H[i - 1];
for (int i = 1; i <= n; ++i) st[i][0] = i;
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i <= n - (1 << j) + 1; ++i) {
int id1 = st[i][j - 1], id2 = st[i + (1 << j - 1)][j - 1];
st[i][j] = (a[id1] > a[id2] ? id1 : id2);
}
}
vector <int> ss;
for (int i = 1; i <= n; ++i) {
while (!ss.empty() && a[ss.back()] < a[i]) rst[ss.back()] = i, ss.pop_back();
ss.push_back(i);
}
ss.clear();
for (int i = n; i >= 1; --i) {
while (!ss.empty() && a[ss.back()] < a[i]) lst[ss.back()] = i, ss.pop_back();
ss.push_back(i);
}
for (int i = 1; i <= n; ++i) {
jump[i][0] = (a[lst[i]] > a[rst[i]] ? lst[i] : rst[i]);
//cout << jump[i][0] << ' ';
// cout << rst[i] << ' ';
} //cout << '\n';
for (int j = 1; j < 20; ++j) {
for (int i = 1; i <= n; ++i)
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
return;
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
int idx = -1;
int ans = -1;
int l = A, r = B, maxl = a[get(C, D)];
while (l <= r) {
int mid = (l + r)/2;
int idd = get(mid, B);
if (a[idd] < maxl) idx = idd, r = mid - 1;
else l = mid + 1;
}
if (idx == -1) return -1;
//cout << ":" << A << ' ' << B << ' ' << maxl << ' ' << idx << '\n';
l = 0, r = n;
while (l <= r) {
int mid = (l + r)/2;
int pos = idx;
for (int i = 0; (1 << i) <= mid; ++i) {
if (mid & (1 << i)) pos = jump[pos][i];
}
//cout << mid << ' ' << pos << '\n';
if (pos == 0 || rst[pos] == 0 || pos > D || (rst[pos] >= C && rst[pos] <= D)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans + 1;
}
