#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 200004;
const int lg = 18;
int lef[nax][lg], rit[nax][lg], hi[nax][lg];
int a[nax];
void init(int N, vector<int> H) {
for(int i=0; i<N; ++i) {
a[i] = H[i];
}
stack<int>st;
for(int i=0; i<N; ++i) {
lef[i][0] = rit[i][0] = hi[i][0] = i;
}
for(int i=0; i<N; ++i) {
while(!st.empty() && H[st.top()]<a[i]) {
rit[st.top()][0] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=N-1; i>=0; --i) {
while(!st.empty() && H[st.top()]<a[i]) {
lef[st.top()][0] = i;
st.pop();
}
st.push(i);
}
for(int i=0; i<N; ++i) {
hi[i][0] = (H[lef[i][0]]>H[rit[i][0]]) ? lef[i][0] : rit[i][0];
}
for(int j=1; j<lg; ++j) {
for(int i=0; i<N; ++i) {
lef[i][j] = lef[lef[i][j-1]][j-1];
rit[i][j] = rit[rit[i][j-1]][j-1];
hi[i][j] = hi[hi[i][j-1]][j-1];
}
}
}
int getMAX(int C, int D) {
int at = C;
for(int j=lg-1; j>=0; --j) {
if(rit[at][j]<=D) {
at = rit[at][j];
}
}
return a[at];
}
int getStart(int A, int B, int mx) {
int at = B;
for(int j=lg-1; j>=0; --j) {
if(lef[at][j]>=A && a[lef[at][j]]<mx) {
at = lef[at][j];
}
}
return at;
}
int finish(int at, int C, int D) {
int ret = 0;
for(int j=lg-1; j>=0; --j) {
if(rit[at][j]<C) {
ret |= 1<<j;
at = rit[at][j];
}
}
++ret;
at = rit[at][0];
return ret;
}
int minimum_jumps(int A, int B, int C, int D) {
int mx = getMAX(C, D);
int l = getStart(A, B, mx);
if(a[l]>mx) return -1;
int ans = 0;
int cur = l;
for(int j=lg-1; j>=0; --j) {
int at = hi[cur][j];
if(a[at]>=mx) continue;
if(rit[at][0]>=C) continue;
cur = at;
ans |= 1<<j;
}
int np = finish(cur, C, D);
if(a[hi[cur][0]]<=mx) {
np = min(finish(hi[cur][0], C, D)+1, np);
}
if(np==-1) return -1;
ans += np;
return ans;
}
