#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int MAXB = 20;
typedef pair<int, int> pii;
int height[MAXN];
int great[MAXN][2];
int nxt[MAXN][MAXB];
int depth[MAXN];
int n;
int get_max(int i, int j) { // returns rightmost in case
if (i == -1) return j;
if (j == -1) return i;
return height[i] > height[j] ? i : j;
}
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
int mx = 0;
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp < rp) {
int m = (lp+rp)/2;
l = new stree(lp, m);
r = new stree(m+1, rp);
reupd();
}
else mx = lp;
}
void reupd() {
mx = get_max(l->mx, r->mx);
}
int range_mx(int lv, int rv) {
if (lp > rv || rp < lv) return -1;
if (lp >= lv && rp <= rv) return mx;
return get_max(l->range_mx(lv, rv), r->range_mx(lv, rv));
}
int right_mx(int lv, int rv, int v) { // rightmost pos in lv...rv st height[i] > v
if (lp > rv || rp < lv || height[mx] < v) return -1;
if (lp == rp) return lp;
int rq = r->right_mx(lv, rv, v);
return rq == -1 ? l->right_mx(lv, rv, v) : rq;
}
};
stree *tree;
void init(int N, vector<int> H) {
n = N;
height[n] = MAXN;
for (int i = 0; i < n; i++) height[i] = H[i];
tree = new stree(0, n-1);
vector<int> rvals;
depth[n] = 0;
rvals.push_back(n);
for (int i = n-1; i >= 0; i--) {
while (height[i] > height[rvals.back()]) rvals.pop_back();
great[i][0] = rvals.back();
depth[i] = 1+depth[rvals.back()];
rvals.push_back(i);
}
rvals.clear();
rvals.push_back(-1);
for (int i = 0; i < n; i++) {
while (rvals.size() > 1 && height[i] > height[rvals.back()]) rvals.pop_back();
great[i][1] = rvals.back();
rvals.push_back(i);
}
for (int i = 0; i < n; i++) {
nxt[i][0] = i;
if (great[i][0] < n) nxt[i][0] = get_max(great[i][0], nxt[i][0]);
if (great[i][1] >= 0) nxt[i][0] = get_max(great[i][1], nxt[i][0]);
}
for (int j = 1; j < MAXB; j++) {
for (int i = 0; i < n; i++) {
nxt[i][j] = nxt[nxt[i][j-1]][j-1];
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
int rmx = height[tree->range_mx(c, d)];
if (height[b] > rmx) return -1;
if (c == b+1) {
return 1;
}
int dpos = tree->range_mx(b+1, c-1);
int div = height[dpos];
if (div > rmx) return -1;
int lmx = tree->range_mx(a, b);
int lgreat = tree->right_mx(0, b, div);
int s = lmx;
if (lgreat >= a) {
if (height[lgreat] < rmx) return 1;
s = tree->range_mx(lgreat+1, b);
}
int mv = 0;
for (int i = MAXB-1; i >= 0; i--) {
if (height[nxt[s][i]] <= div) {
s = nxt[s][i];
mv += (1<<i);
}
}
// now, we either go to the left or we go to the right
if (height[s] == div) return 1+mv;
assert(lgreat != -1);
if (height[lgreat] < rmx) return 2+mv;
return mv+1+depth[s]-depth[dpos];
}
