#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];
set<pair<int, int>> t[800005];
void update(int v, int tl, int tr, int x) {
t[v].insert({a[x], x});
if (tl == tr) {
return;
}
int mid = (tl + tr) >> 1;
if (mid >= x) update(v << 1, tl, mid, x);
else update(v << 1 | 1, mid + 1, tr, x);
}
int sum(int v, int tl, int tr, int l, int r, int x) {
if (l > r) return 0;
if (tl == l && tr == r) {
if ((*t[v].rbegin()).first < x) return 0;
return (*t[v].lower_bound({x + 1, 0})).second;
}
int mid = (tl + tr) >> 1;
int h = sum(v << 1, tl, mid, l, min(r, mid), x), k = sum(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x);
if (a[h] > a[k]) return k;
return h;
}
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++) {
update(1, 1, 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], 0};
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]][0][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) {
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;
}
int check(int x, int y) {
for (int i = 17; i >= 0; i--) {
int h = p[x][1][i];
if (a[h] > a[y]) continue;
x = h;
}
if (x == y) return 1;
return 0;
}
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.second != y) {
pair<int, int> v = trya(u.second + 1, y);
if (v.first > hh.first) {
int h = sum(1, 1, n, u.second, y, hh.first);
h = p[h][1][0];
if (z <= h && h <= t) return 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;
}
