#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], go[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) {
lst[0] = rst[0] = 0;
for (int i = 1; i <= n; ++i) {
a[i] = H[i - 1];
lst[i] = rst[i] = 0;
}
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]);
go[i][0] = rst[i];
}
for (int j = 1; j < 20; ++j) {
for (int i = 1; i <= n; ++i)
jump[i][j] = jump[jump[i][j - 1]][j - 1],
go[i][j] = go[go[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 = 0, res = 0;
int l = A, r = B, maxl = a[get(C, D)];
if (C > B + 1 && a[get(B + 1, C - 1)] > maxl) return -1;
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;
l = 0, r = n;
int idd = idx;
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];
}
if (a[pos] > maxl || pos == 0 || pos >= C) {
r = mid - 1;
continue;
}
if (rst[pos] >= C) {
idd = pos;
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = 0, r = n; int add = 0;
while (l <= r) {
int mid = (l + r)/2;
int pos = idd;
for (int i = 0; (1 << i) <= mid; ++i) {
if (mid & (1 << i)) pos = go[pos][i];
}
if (pos == 0 || pos >= C) add = mid, r = mid - 1;
else l = mid + 1;
}
ans += add;
l = 0, r = n, idd = idx;
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];
}
if (a[pos] > maxl || pos == 0 || pos >= C) {
r = mid - 1;
continue;
}
res = mid, idd = pos, l = mid + 1;
}
l = 0, r = n, add = 0;
while (l <= r) {
int mid = (l + r)/2;
int pos = idd;
for (int i = 0; (1 << i) <= mid; ++i) {
if (mid & (1 << i)) pos = go[pos][i];
}
if (pos == 0 || pos >= C) add = mid, r = mid - 1;
else l = mid + 1;
}
res += add;
return min(ans, res);
}
