#include <bits/stdc++.h>
using namespace std;
#include "jumps.h"
#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
#define FI first
#define SE second
#define MP make_pair
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif
#define INF 1000000005
#define MAXN 200005
#define MAXL 20
int n;
vi h;
int lft[MAXL][MAXN], rht[MAXL][MAXN], big[MAXL][MAXN];
ii sp[MAXL][MAXN];
inline ii qsp(int s, int e) {
int k = 31 - __builtin_clz(e - s + 1);
return max(sp[k][s], sp[k][e - (1 << k) + 1]);
}
void init(int _n, vi _h) {
n = _n;
h = _h;
{
stack<int> stk;
REP (i, 0, n) {
while (!stk.empty() && h[stk.top()] < h[i]) {
stk.pop();
}
if (!stk.empty()) {
lft[0][i] = stk.top();
} else {
lft[0][i] = -1;
}
stk.push(i);
}
}
{
stack<int> stk;
RREP (i, n - 1, 0) {
while (!stk.empty() && h[stk.top()] < h[i]) {
stk.pop();
}
if (!stk.empty()) {
rht[0][i] = stk.top();
} else {
rht[0][i] = -1;
}
stk.push(i);
}
}
REP (i, 0, n) {
if (lft[0][i] == -1 || rht[0][i] == -1) {
big[0][i] = -1;
}
if (h[lft[0][i]] > h[rht[0][i]]) {
big[0][i] = lft[0][i];
} else {
big[0][i] = rht[0][i];
}
}
REP (k, 1, MAXL) {
REP (i, 0, n) {
if (lft[k - 1][i] == -1) {
lft[k][i] = -1;
} else {
lft[k][i] = lft[k - 1][lft[k - 1][i]];
}
if (rht[k - 1][i] == -1) {
rht[k][i] = -1;
} else {
rht[k][i] = rht[k - 1][rht[k - 1][i]];
}
if (big[k - 1][i] == -1) {
big[k][i] = -1;
} else {
big[k][i] = big[k - 1][big[k - 1][i]];
}
}
}
REP (i, 0, n) {
sp[0][i] = MP(h[i], i);
}
REP (k, 1, MAXL) {
REP (i, 0, n - (1 << k - 1)) {
sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
if (b + 1 == c) {
if (rht[0][b] == -1 || rht[0][b] > d) {
return -1;
} else {
return 1;
}
}
int rmx = qsp(c, d).FI, mmx = qsp(b + 1, c - 1).FI;
if (mmx > rmx) {
return -1;
}
int u = b;
if (h[u] >= rmx) {
return -1;
}
RREP (k, MAXL - 1, 0) {
if (lft[k][u] == -1) continue;
if (lft[k][u] >= a && h[lft[k][u]] < rmx) {
u = lft[k][u];
}
}
assert(h[u] < rmx);
if (h[u] > mmx) {
assert(rht[0][u] >= c && rht[0][u] <= d);
return 1;
}
int ans = 0;
RREP (k, MAXL - 1, 0) {
if (big[k][u] == -1) continue;
if (h[big[k][u]] < mmx) {
u = big[k][u];
ans += 1 << k;
}
}
if (big[0][u] != -1 && h[big[0][u]] <= rmx) {
assert(h[big[0][u]] >= mmx);
assert(rht[0][big[0][u]] >= c && rht[0][big[0][u]] <= d);
return ans + 2;
}
RREP (k, MAXL - 1, 0) {
if (rht[k][u] == -1) continue;
if (rht[k][u] < c) {
u = rht[k][u];
ans += 1 << k;
}
}
if (rht[0][u] <= d) {
assert(rht[0][u] >= c);
return ans + 1;
} else {
return -1;
}
}
/*
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
*/
