#include "jumps.h"
#include <stack>
#include <vector>
#include <iostream>
#include <queue>
const int MAXN = 200010;
int L[MAXN], R[MAXN];
int N_;
int mi[19][MAXN], ma[19][MAXN], rr[19][MAXN];
bool st1;
int V[MAXN];
std::pair<int, int> str[4 * MAXN];
void u(int l, int r, int tar, int idx, int val) {
if(l == r) {
str[idx] = {val, tar}; return;
}
int mid = (l + r) >> 1;
if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
else u(mid+1, r, tar, 2*idx+2, val);
str[idx] = max(str[2*idx+1], str[2*idx+2]);
}
std::pair<int, int> qu1(int l, int r, int constl, int constr, int idx) {
if(l<=constl && constr<=r) return str[idx];
int mid = (constl+constr) >> 1;
if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid+1) return qu1(l, r, constl, mid, 2*idx+1);
else return max(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
}
int qu2(int l, int r, int constl, int constr, int idx, int val) {
if(l<=constl && constr<=r) {
if(str[idx].first <= val) {
return -1;
}
while(constl < constr) {
int mid = (constl + constr) >> 1;
if(str[2*idx+2].first > val) constl = mid + 1, idx = 2 * idx + 2;
else constr = mid, idx = 2 * idx + 1;
}
return constl;
}
int mid = (constl+constr) >> 1;
if(mid<l || r< constl) return qu2(l, r, mid+1, constr, 2*idx+2, val);
else if(constr< l || r< mid+1) return qu2(l, r, constl, mid, 2*idx+1, val);
else {
int res = qu2(l, r, mid+1, constr, 2*idx+2, val);
if(res != -1) return res;
return qu2(l, r, constl, mid, 2*idx+1, val);
}
}
void update(int i, int v) {
u(0, N_ - 1, i, 0, v);
}
int query_max(int l, int r) {
return qu1(l, r, 0, N_ - 1, 0).second;
}
int last_greater(int l, int r, int c) {
return qu2(l, r, 0, N_ - 1, 0, c);
}
void init(int N, std::vector<int> H) {
N_ = N;
for(int i=0; i<N; i++) update(i, H[i]);
st1 = 1;
for(int i=0; i<N; i++) {
L[i] = R[i] = -1;
V[i] = H[i];
if(H[i] != i + 1) st1 = 0;
}
std::stack<int> st;
for(int i=0; i<N; i++) {
while(st.size() && H[st.top()] < H[i]) {
st.pop();
}
if(st.size()) L[i] = st.top();
st.push(i);
}
while(st.size()) st.pop();
for(int i=N-1; i>=0; i--) {
while(st.size() && H[st.top()] < H[i]) {
st.pop();
}
if(st.size()) R[i] = st.top();
st.push(i);
}
while(st.size()) st.pop();
for(int i=0; i<N; i++) {
rr[0][i] = R[i];
}
for(int i=0; i<N; i++) {
if(L[i] == -1 && R[i] == -1) {
mi[0][i] = ma[0][i] = -1;
}
else if(L[i] == -1) {
mi[0][i] = ma[0][i] = R[i];
}
else if(R[i] == -1) {
mi[0][i] = ma[0][i] = L[i];
}
else {
mi[0][i] = (H[L[i]] < H[R[i]] ? L[i] : R[i]);
ma[0][i] = (H[L[i]] > H[R[i]] ? L[i] : R[i]);
}
}
for(int i=1; i<19; i++) {
for(int j=0; j<N; j++) {
if(mi[i-1][j] == -1) mi[i][j] = -1;
else mi[i][j] = mi[i-1][mi[i-1][j]];
if(ma[i-1][j] == -1) ma[i][j] = -1;
else ma[i][j] = ma[i-1][ma[i-1][j]];
if(rr[i-1][j] == -1) rr[i][j] = -1;
else rr[i][j] = rr[i-1][rr[i-1][j]];
}
}
}
int qcnt = 0;
int minimum_jumps(int A, int B, int C, int D) {
if(V[query_max(B, C - 1)] > V[query_max(C, D)]) return -1;
int lg = last_greater(A, B, V[query_max(C, D)]);
if(lg == -1) lg = A - 1;
A = query_max(lg+1, B);
//std::cout << A << " !!! ";
int X = V[query_max(B, C - 1)];
int Y = V[query_max(C, D)];
int ans = 0;
//std::cout << X << " " << Y << " ";
for(int i=18; i>=0; i--) {
if(ma[i][A] != -1) {
if(V[ma[i][A]] < X) {
ans += (1 << i);
A = ma[i][A];
}
}
}
if(C <= rr[0][A] && rr[0][A] <= D) return ans + 1;
if(ma[0][A] != -1 && X <= V[ma[0][A]] && V[ma[0][A]] < Y) {
return ans + 2;
}
int lb = 0, rb = (1 << 19) - 1;
while(lb < rb) {
int mid = (lb + rb) >> 1;
bool ok = 1;
int sto = A;
for(int i=18; i>=0; i--) {
if(!(mid & (1 << i))) continue;
if(rr[i][sto] != -1) {
if(V[rr[i][sto]] <= Y) {
sto = rr[i][sto];
}
}
else {
ok = 0; break;
}
}
//std::cout << "Steps " << mid << " res " << sto << " flag " << ok << "\n";
if(C <= sto || !ok)rb = mid;
else lb = mid+ 1;
}
if(rb != (1 << 19) - 1) return ans+ lb;
return -1;
}
