#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200009, L = 18;
int n, lg[N], h[N], o[N][L], mx[N][L], t[N][L], p[N], lft[N], rgt[N];
int get_max(int l, int r) {
int d = lg[r - l + 1];
return max(mx[l][d], mx[r - (1 << d) + 1][d]);
}
void init(int n_, vector < int > h_) {
n = n_;
for (int i = 1; i <= n; i++) h[i] = h_[i - 1];
for (int i = 1; i <= n; i++) {
p[h[i]] = i;
mx[i][0] = h[i];
if (i > 1) lg[i] = lg[i >> 1] + 1;
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
vector < int > v;
for (int i = 1; i <= n; i++) {
while (!v.empty() && h[v.back()] <= h[i]) v.pop_back();
if (v.empty()) lft[i] = 1; else lft[i] = v.back();
v.push_back(i);
}
v.clear();
for (int i = n; i >= 1; i--) {
while (!v.empty() && h[v.back()] <= h[i]) v.pop_back();
if (v.empty()) rgt[i] = n; else rgt[i] = v.back();
v.push_back(i);
}
for (int i = 1; i <= n; i++) {
o[i][0] = (h[lft[i]] > h[rgt[i]] ? lft[i] : rgt[i]);
t[i][0] = rgt[i];
}
for (int j = 1; j < L; j++) {
for (int i = 1; i <= n; i++) {
o[i][j] = o[o[i][j - 1]][j - 1];
t[i][j] = t[t[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int l, int r, int lg, int rg) {
l++, r++, lg++, rg++;
int i = lft[lg];
if (i >= r) return -1;
int j = max(i + 1, l);
int x = get_max(j, r);
j = p[x];
int res = 0;
for (int l = L - 1; l >= 0; l--) if (h[o[j][l]] < h[lg]) j = o[j][l], res += (1 << l);
for (int l = L - 1; l >= 0; l--) if (t[j][l] < lg) j = t[j][l], res += (1 << l);
return res + 1;
}
