#include "jumps.h"
#include <vector>
#include <iostream>
#include <stack>
using namespace std;
const int maxN = 200'000;
const int logN = 18;
const int INF = 1e9;
int N;
vector<int> H(2+maxN);
vector<int> leftHigh(2+maxN);
vector<int> rightHigh(2+maxN);
vector< vector<int> > highEdge(2+maxN, vector<int>(logN));
vector< vector<int> > lowEdge(2+maxN, vector<int>(logN));
vector< vector<int> > rightEdge(2+maxN, vector<int>(logN));
vector< vector<int> > highEdge_highmax(2+maxN, vector<int>(logN));
vector< vector<int> > highEdge_lowmax(2+maxN, vector<int>(logN));
struct segtree
{
int l;
int r;
int mn = -INF;
int mx = INF;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
{
mn = mx = H[l];
}
else
{
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
mn = min(left->mn, right->mn);
mx = max(left->mx, right->mx);
}
}
int rangemax(int L, int R)
{
if(R < l || r < L) return -INF;
else if(L <= l && r <= R) return mx;
else return max(left->rangemax(L, R), right->rangemax(L, R));
}
int rangemin(int L, int R)
{
if(R < l || r < L) return INF;
else if(L <= l && r <= R) return mn;
else return min(left->rangemin(L, R), right->rangemin(L, R));
}
};
segtree ST;
void init(int n, vector<int> h)
{
N = n;
H[0] = H[N+1] = INF;
for(int i = 1; i <= N; i++) H[i] = h[i-1];
stack<int> S;
leftHigh[0] = 0;
S.push(0);
for(int i = 1; i <= N; i++)
{
while(!S.empty() && H[S.top()] < H[i])
S.pop();
if(!S.empty()) leftHigh[i] = S.top();
S.push(i);
}
while(!S.empty()) S.pop();
leftHigh[N+1] = N+1;
rightHigh[N+1] = N+1;
S.push(N+1);
for(int i = N; i >= 1; i--)
{
while(!S.empty() && H[S.top()] < H[i])
S.pop();
if(!S.empty()) rightHigh[i] = S.top();
S.push(i);
}
leftHigh[0] = 0;
// for(int i = 0; i <= N+1; i++) cerr << leftHigh[i] << ' ';
// cerr << '\n';
// for(int i = 0; i <= N+1; i++) cerr << rightHigh[i] << ' ';
// cerr << '\n';
highEdge[0][0] = 0;
lowEdge[0][0] = 0;
rightEdge[0][0] = 0;
highEdge_highmax[0][0] = 0;
highEdge_lowmax[0][0] = 0;
for(int i = 1; i <= N; i++)
{
highEdge[i][0] = (H[ leftHigh[i] ] > H[ rightHigh[i] ]) ? leftHigh[i] : rightHigh[i];
lowEdge[i][0] = (H[ leftHigh[i] ] < H[ rightHigh[i] ]) ? leftHigh[i] : rightHigh[i];
rightEdge[i][0] = rightHigh[i];
}
for(int i = 1; i <= N; i++)
{
highEdge_highmax[i][0] = highEdge[i][0];
highEdge_lowmax[i][0] = lowEdge[i][0];
}
highEdge[N+1][0] = N+1;
lowEdge[N+1][0] = N+1;
rightEdge[N+1][0] = N+1;
highEdge_highmax[N+1][0] = N+1;
highEdge_lowmax[N+1][0] = N+1;
for(int e = 1; e < logN; e++)
{
for(int i = 0; i <= N+1; i++)
{
highEdge[i][e] = highEdge[ highEdge[i][e-1] ][e-1];
lowEdge[i][e] = lowEdge[ lowEdge[i][e-1] ][e-1];
rightEdge[i][e] = rightEdge[ rightEdge[i][e-1] ][e-1];
highEdge_highmax[i][e] = max(highEdge_highmax[i][e-1], highEdge_highmax[ highEdge[i][e-1] ][e-1]);
highEdge_lowmax[i][e] = max(highEdge_lowmax[i][e-1], highEdge_lowmax[ highEdge[i][e-1] ][e-1]);
}
}
ST = segtree(0, N+1);
}
int minimum_jumps(int A, int B, int C, int D)
{
A++;
B++;
C++;
D++;
int oldB = B;
int CDmax = ST.rangemax(C, D);
if(ST.rangemax(B, oldB) > CDmax) return -1;
while(A != B)
{
int m = (A+B)/2;
if(ST.rangemax(m, oldB) <= CDmax) B = m;
else A = m+1;
}
for(int bit = logN-1; bit >= 0; bit--)
{
int newA = A + (1 << bit);
if(newA > oldB) continue;
if(ST.rangemax(A, oldB) == ST.rangemax(newA, oldB)) A = newA;
}
// cerr << "A = B = " << A << '\n';
int o = A;
int res = 0;
// while(1)
// {
// if(C <= o && o <= D) return res;
// else if(o > D || H[o] > CDmax) return -1;
// else if(highEdge[o][0] < C && H[highEdge[o][0]] <= CDmax && lowEdge[o][0] < C)
// {
// o = highEdge[o][0];
// res++;
// }
// else
// {
// o = rightEdge[o][0];
// res++;
// }
// }
for(int bit = logN-1; bit >= 0; bit--)
{
if(C <= o && o <= D) return res;
else if(o > D || H[o] > CDmax) return -1;
else if(highEdge_highmax[o][bit] < C && H[highEdge[o][bit]] <= CDmax && highEdge_lowmax[o][bit] < C)
{
o = highEdge[o][bit];
res += (1 << bit);
}
}
for(int bit = logN-1; bit >= 0; bit--)
{
if(C <= o && o <= D) return res;
else if(o > D || H[o] > CDmax) return -1;
else if(rightEdge[o][bit] < C)
{
o = rightEdge[o][bit];
res += (1 << bit);
}
}
if(o < C)
{
o = rightEdge[o][0];
res++;
}
if(D < o) return -1;
return res;
}
