#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
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) {
n = _n;
for (int i = 0; i <= n; i++) {
lst[i] = rst[i] = 0;
for (int j = 0; j < 20; j++) {
jump[i][j] = go[i][j] = 0;
}
}
a[0] = 0;
for (int i = 1; i <= n; ++i) a[i] = H[i - 1], 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];
int 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 = 0; j < 20; j++) {
jump[0][j] = 0;
go[0][j] = 0;
}
for (int j = 1; j < 20; ++j) {
for (int i = 1; i <= n; ++i) {
if (jump[i][j - 1] == 0) jump[i][j] = 0;
else jump[i][j] = jump[jump[i][j - 1]][j - 1];
if (go[i][j - 1] == 0) go[i][j] = 0;
else go[i][j] = go[go[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
int idx = -1, ans = 0, res = 0, 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 (pos == 0) break;
if (mid & (1 << i)) pos = jump[pos][i];
}
if (pos == 0 || a[pos] > maxl || 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 (pos == 0) break;
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 (pos == 0) break;
if (mid & (1 << i)) pos = jump[pos][i];
}
if (pos == 0 || a[pos] > maxl || 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 (pos == 0) break;
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);
}
