#include <bits/stdc++.h>
using namespace std;
int n, a[200005], p[200005][2][18], ll[200005];
pair<int, int> l[200005][18], pp[200005][18];
void init(int N, vector<int> aa) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = aa[i - 1];
}
for (int i = 2; i <= n; i++) ll[i] = ll[i / 2] + 1;
a[0] = a[n + 1] = 1e9;
stack<int> s;
for (int i = 1; i <= n; i++) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (s.empty()) p[i][0][0] = 0;
else p[i][0][0] = s.top();
s.push(i);
pp[i][0] = {a[i], i};
}
while (!s.empty()) s.pop();
for (int i = n; i >= 1; i--) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (s.empty()) p[i][1][0] = n + 1;
else p[i][1][0] = s.top();
int h = p[i][0][0], k = p[i][1][0];
if (a[h] > a[k]) l[i][0] = {a[h], h};
else l[i][0] = {a[k], k};
s.push(i);
}
p[n + 1][0][0] = p[n + 1][1][0] = n + 1;
l[0][0] = {a[0], 0}; l[n + 1][0] = {a[n + 1], n + 1};
for (int i = 1; i <= 17; i++) {
for (int j = 0; j <= n + 1; j++) {
p[j][0][i] = p[p[j][0][i - 1]][0][i - 1];
p[j][1][i] = p[p[j][1][i - 1]][1][i - 1];
}
for (int j = 0; j <= n + 1; j++) {
l[j][i] = l[l[j][i - 1].second][i - 1];
}
for (int j = 1; j <= n - (1 << i) + 1; j++) {
pp[j][i] = max(pp[j][i - 1], pp[j + (1 << (i - 1))][i - 1]);
}
}
}
int travel(int x, int y) {
if (a[y] < a[x]) return 1e9;
int c = 0;
for (int i = 17; i >= 0; i--) {
if (l[x][i].first > a[y]) continue;
x = l[x][i].second;
c += (1 << i);
}
if (x < y) {
for (int i = 17; i >= 0; i--) {
int h = p[x][1][i];
if (a[h] > a[y]) continue;
x = h;
c += (1 << i);
}
}
else {
for (int i = 17; i >= 0; i--) {
int h = p[x][0][i];
if (a[h] > a[y]) continue;
x = h;
c += (1 << i);
}
}
return c;
}
pair<int, int> trya(int x, int y) {
if (x > y) return {0, 0};
int h = ll[y - x + 1];
return max(pp[x][h], pp[y - (1 << h) + 1][h]);
}
int minimum_jumps(int x, int y, int z, int t) {
x++; y++; z++; t++;
pair<int, int> hh = trya(y + 1, z - 1), u = trya(x, y);
int mi = 1e9;
if (u.first > hh.first) {
int l = u.second, r = y, res = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (trya(mid, y).first >= hh.first) {
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
int h = res;
h = p[h][1][0];
if (z <= h && h <= t) return 1;
}
if (u.second != y) {
if (z <= p[hh.second][1][0] && p[hh.second][1][0] <= t) {
int l = u.second + 1, r = y, res = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (trya(mid, y).first < hh.first) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (res != 0) {
int h = trya(res, y).second;
mi = min(mi, travel(h, hh.second) + 1);
}
}
}
int h = u.second;
for (int i = 17; i >= 0; i--) {
if (a[p[h][0][i]] >= hh.first) continue;
h = p[h][0][i];
}
h = p[h][0][0];
if (h != 0) {
if (z <= p[h][1][0] && p[h][1][0] <= t) {
mi = min(mi, travel(u.second, h) + 1);
}
}
if (z <= p[hh.second][1][0] && p[hh.second][1][0] <= t) {
mi = min(mi, travel(u.second, hh.second) + 1);
}
if (mi == 1e9) return -1;
return mi;
}
