#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "jumps.h"
using namespace std;
#define ll long long
const int N = 200'005;
int nxt[N], prv[N], lift[N][18], n;
vector<int> a;
bool ST1 = 1;
void init(int _n, vector<int> _a) {
a = _a;
n = _n;
for (int i = 0; i < n; i++) {
ST1 &= a[i] == i + 1;
}
stack<int> s;
s.push(n);
for (int i = n - 1; i >= 0; i--) {
while (s.top() != n && a[s.top()] < a[i]) {
s.pop();
}
nxt[i] = s.top();
s.push(i);
}
while (s.size()) s.pop();
s.push(-1);
for (int i = 0; i < n; i++) {
while (s.top() != -1 && a[s.top()] < a[i]) {
s.pop();
}
prv[i] = s.top();
s.push(i);
}
for (int i = 0; i < n; i++) {
if (prv[i] == -1 || a[nxt[i]] > a[prv[i]]) {
lift[i][0] = nxt[i];
} else {
lift[i][0] = prv[i];
}
}
lift[n][0] = n;
for (int j = 1; j < 18; j++) {
for (int i = 0; i <= n; i++) {
lift[i][j] = lift[lift[i][j - 1]][j - 1];
}
}
}
int minimum_jumps(int l, int r, int s, int e) {
#ifndef MINA
if (ST1) {
return s - r;
}
#endif
if (nxt[r] > e) {
return -1;
}
int mx = -1, lst = -1;
for (int i = r; i >= l; i--) {
if (a[i] > mx) {
mx = a[i];
if (nxt[i] <= e) {
lst = i;
} else {
break;
}
}
}
if (lst == -1) return -1;
int cur = lst, ans = 0;
for (int j = 17; j >= 0; j--) {
int New = lift[cur][j];
if (New != n && nxt[New] < s) {
cur = New;
ans += 1 << j;
}
}
if (nxt[lift[cur][0]] <= e && nxt[cur] < s) {
cur = lift[cur][0];
ans++;
}
while (cur < s) {
cur = nxt[cur];
ans++;
}
// bool ok = 0;
// while (cur < s) {
// if (ok || nxt[cur] >= s || prv[cur] == -1 || a[nxt[cur]] > a[prv[cur]] || nxt[prv[cur]] > e) {
// if (prv[cur] == -1 || nxt[prv[cur]] > e) {
// ok = 1;
// }
// cur = nxt[cur];
// } else {
// cur = prv[cur];
// }
// ans++;
// }
if (cur > e) {
return -1;
}
return ans;
}
