#include "jumps.h"
using namespace std;
#include <vector>
#include <stack>
#include <algorithm>
#define vi vector<int>
const int siz = 2e5 + 2;
#define pi pair<int,int>
#define x first
#define y second
struct node {
int l, r, mid;
pi maxi ={0,0};
node* sl=NULL, * sr=NULL;
node(int li, int ri) {
l = li, r = ri, mid = (l + r) / 2;
}
void ini() {
if (l < r) {
sl = new node(l, mid);
sr = new node(mid + 1, r);
sl->ini(); sr->ini();
}
}
void open(int i, pi val, node* no) {
maxi = max(no->maxi, val);
if (l < r) {
if (i <= mid) {
sr = no->sr;
sl = new node(l, mid); sl->open(i, val, no->sl);
}
else {
sl = no->sl;
sr = new node(mid + 1, r); sr->open(i, val, no->sr);
}
}
}
pi query(int a, int b) {
if (a > b)return { 0,0 };
if (a > r || b < l) return { 0,a };
if (a <= l && b >= r)return maxi;
return max(sl->query(a,b), sr->query(a,b));
}
};
node* seg[siz];
int h[siz];
int bin[siz][20][2];
int l[siz], r[siz];
int n;
int ll[siz], rr[siz];
void init(int N, std::vector<int> H) {
seg[0] = new node(0, N);
n = N;
seg[0]->ini();
vi his(N + 1);
for (int i = 0; i < N; i++)h[i] = H[i];
for (int i = 0; i < N; i++)his[H[i]] = i;
for (int i = 1; i <= N; i++) {
seg[i] = new node(0, N);
seg[i]->open(his[i], { i,his[i] }, seg[i - 1]);
}
stack<pi> s; s.push({ 1e9,-1 });
for (int i = 0; i < N; i++) {bin[i][0][0] = -1, bin[i][0][1] = -1;}
for (int i = 0; i < N; i++) {
while (s.top().x < h[i]) {
s.pop();
}
l[i] = s.top().y;
ll[i] = s.top().x;
s.push({ h[i],i });
}
while (s.size() > 1)s.pop();
for (int i = N - 1; i >= 0; i--) {
while (s.top().x < h[i]) {
s.pop();
}
r[i] = s.top().y;
rr[i] = s.top().x;
s.push({ h[i],i });
}
for (int i = 0; i < N; i++) {
if (rr[i] == 1e9)rr[i] = -1; if (ll[i] == 1e9)ll[i] = -1;
if (rr[i] < ll[i]) {
swap(ll[i], rr[i]); swap(l[i], r[i]);
}
bin[i][0][1] = r[i];
if (l[i] == -1)bin[i][0][0] = r[i]; else bin[i][0][0] = l[i];
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i < N; i++) {
for (int k = 0; k < 2; k++) {
if (bin[i][j - 1][k] >= 0)bin[i][j][k] = bin[bin[i][j - 1][k]][j - 1][k];
else bin[i][j][k] = -1;
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0;
int m, mid; pi ps;
m = seg[n]->query(C, D).x;
//ps = seg[m - 1]->query(A, B);
int ss = A, e = B;
while (ss < e) {
int midmid = (ss + e) / 2;
pi p = seg[n]->query(midmid, B);
if (p.x > m) {
ss = midmid + 1;
}
else e = midmid;
}
ps = seg[n]->query(ss, B);
mid = seg[n]->query(B + 1, C - 1).x;
//m = h[C]; ps = { h[A],A }; if (h[A] > h[C])ps.x = 0; mid = 0; for (int i = B + 1; i < C; i++)mid = max(mid, h[i]);
int s = ps.y;
if (ps.x>m)return -1;
if (C == B + 1)return 1;
if (mid > m)return -1;
if (mid < ps.x)return 1;
for (int d = 19; d >= 0; d--) {
int st = bin[s][d][1];
if (st != -1) {
if (h[st] < mid) {
s = st;
ans += (1 << d);
}
}
}
if (h[bin[s][0][1]] < m)return ans + 2;
for (int d = 19; d >= 0; d--) {
int st = bin[s][d][0];
if (st != -1) {
if (h[st] < mid) {
s = st;
ans += (1 << d);
}
}
}
return ans + 2;
}
