#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 7;
const int inf = (int) 1e9 + 7;
int n, a[N], lft[N], rgh[N];
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];
}
{
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 sol = inf, y = max_element(a + l2, a + r2 + 1) - a;
for (int x = l1; x <= r1; x++) {
int mx = 0;
for (int j = x + 1; j < l2; j++) {
mx = max(mx, a[j]);
}
if (mx > a[y]) continue;
if (a[x] > a[y]) continue;
int p = x, cost = 0;
while (1) {
assert(a[p] <= a[y]);
cost++;
int p2 = p;
if (rgh[p] && l2 <= rgh[p] && rgh[p] <= r2) {
sol = min(sol, cost);
break;
}
if (lft[p] && a[lft[p]] <= a[y] && a[lft[p]] > a[p2]) p2 = lft[p];
if (rgh[p] && a[rgh[p]] <= a[y] && a[rgh[p]] > a[p2]) p2 = rgh[p];
assert(p2 != p);
assert(a[p] < a[p2]);
p = p2;
}
}
if (sol == inf) {
sol = -1;
}
return sol;
}
