#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 7;
const int K = 20;
const int inf = (int) 1e9 + 7;
int n, a[N], lft[N], rgh[N], position[N], go[N], dist[N];
int rmq[K][N], lg2[N];
int getmax(int l, int r) {
assert(1 <= l && l <= r && r <= n);
int k = lg2[r - l + 1];
return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
void init(int nn, vector<int> hh) {
n = nn;
assert(n == (int) hh.size());
for (int i = 1; i <= n; i++) {
a[i] = hh[i - 1];
position[a[i]] = i;
rmq[0][i] = a[i];
}
for (int i = 2; i <= n; i++) {
lg2[i] = 1 + lg2[i / 2];
}
for (int k = 1; (1 << k) <= n; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
}
}
{
vector<int> stk;
for (int i = 1; i <= n; i++) {
while (!stk.empty() && a[stk.back()] <= a[i]) stk.pop_back();
if (!stk.empty()) lft[i] = stk.back(); else lft[i] = 0;
stk.push_back(i);
}
}
{
vector<int> stk;
for (int i = n; i >= 1; i--) {
while (!stk.empty() && a[stk.back()] <= a[i]) stk.pop_back();
if (!stk.empty()) rgh[i] = stk.back(); else rgh[i] = 0;
stk.push_back(i);
}
}
for (int i = 1; i <= n; i++) {
if (lft[i]) {
assert(a[lft[i]] > a[i]);
}
if (rgh[i]) {
assert(a[rgh[i]] > a[i]);
}
}
}
int minimum_jumps(int l1, int r1, int l2, int r2) {
l1++;
r1++;
l2++;
r2++;
assert(1 <= l1 && l1 <= r1 && r1 < l2 && l2 <= r2 && r2 <= n);
int ymax = getmax(l2, r2);
l1 = max(l1, lft[position[ymax]] + 1);
for (int i = 1; i <= n; i++) {
dist[i] = inf;
}
queue<int> Q;
for (int i = l1; i <= r1; i++) {
dist[i] = 0;
Q.push(i);
}
while (!Q.empty()) {
int X = Q.front(), b = X;
Q.pop();
if (lft[X] && a[lft[X]] <= ymax && a[lft[X]] > a[b]) b = lft[X];
if (rgh[X] && a[rgh[X]] <= ymax && a[rgh[X]] > a[b]) b = rgh[X];
if (dist[b] == inf) {
dist[b] = 1 + dist[X];
Q.push(b);
}
}
int sol = inf;
for (int i = 1; i <= n; i++) {
if (rgh[i] && l2 <= rgh[i] && rgh[i] <= r2) {
sol = min(sol, dist[i] + 1);
}
}
if (sol == inf) {
sol = -1;
}
return sol;
}
