#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][18], prv[N][18], 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][0] = 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][0] = s.top();
s.push(i);
}
for (int i = 0; i < n; i++) {
if (prv[i][0] == -1 || a[nxt[i][0]] > a[prv[i][0]]) {
lift[i][0] = nxt[i][0];
} else {
lift[i][0] = prv[i][0];
}
}
lift[n][0] = n;
nxt[n][0] = n;
prv[n][0] = -1;
for (int j = 1; j < 18; j++) {
for (int i = 0; i <= n; i++) {
lift[i][j] = lift[lift[i][j - 1]][j - 1];
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
prv[i][j] = prv[i][j - 1];
if (prv[i][j] != -1) prv[i][j] = prv[prv[i][j]][j - 1];
}
}
}
int minimum_jumps(int l, int r, int s, int e) {
#ifndef MINA
if (ST1) {
return s - r;
}
#endif
if (nxt[r][0] > e) {
return -1;
}
int lst = r;
for (int j = 17; j >= 0; j--) {
if (l <= prv[lst][j] && nxt[prv[lst][j]][0] <= e) {
lst = prv[lst][j];
}
}
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][0] < s) {
cur = New;
ans += 1 << j;
}
}
if (nxt[lift[cur][0]][0] <= e && nxt[cur][0] < s) {
cur = lift[cur][0];
ans++;
}
for (int j = 17; j >= 0; j--) {
if (nxt[cur][j] < s) {
cur = nxt[cur][j];
ans += 1 << j;
}
}
cur = nxt[cur][0];
ans++;
if (cur > e) {
return -1;
}
return ans;
}
