#include "jumps.h"
#include <vector>
#include <iostream>
#include <math.h>
#include <stack>
#include <cassert>
using namespace std;
const int LOG = 20;
int pl[int(3e5)], pr[int(3e5)];
int high[int(3e5)][LOG], low[int(3e5)][LOG];
int H[int(3e5)];
int spmx[int(3e5)][LOG];
int lg[int(3e5)];
int getmax(int l, int r) {
int j = lg[r - l + 1];
return max(spmx[l][j], spmx[r - (1 << j) + 1][j]);
}
void init(int N, vector<int> a) {
for (int &i : a) i--;
for (int i = 0 ; i < N ; ++ i) H[i] = a[i];
H[N] = N;
stack<int>st;
for (int i = 0 ; i < N ; ++ i) {
while (st.size() && H[st.top()] < H[i]) st.pop();
pl[H[i]] = st.size() ? H[st.top()] : N;
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();
pr[H[i]] = st.size() ? H[st.top()] : N;
st.push(i);
}
pl[N] = pr[N] = N;
for (int i = 0 ; i <= N ; ++ i) {
high[i][0] = max(pl[i], pr[i]);
low[i][0] = pr[i];
//low[i][0] = min(pl[i], pr[i]);
}
for (int j = 1 ; j < LOG ; ++ j) {
for (int i = 0 ; i <= N ; ++ i) {
{
int where = high[i][j - 1];
high[i][j] = high[where][j - 1];
}
{
int where = low[i][j - 1];
low[i][j] = low[where][j - 1];
}
}
}
for (int i = 0 ; i <= N ; ++ i) {
spmx[i][0] = H[i];
}
for (int j = 1 ; j < LOG ; ++ j) {
for (int i = 0 ; i + (1 << j) - 1 <= N ; ++ i) {
spmx[i][j] = max(spmx[i][j - 1], spmx[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 2 ; i < int(3e5) ; ++ i) lg[i] = lg[i >> 1] + 1;
}
int minimum_jumps(int A, int B, int C, int D) {
assert(C == D);
int t = H[C];
int s = -1;
{
int l = A, r = B;
while (l <= r) {
int m = (l + r) >> 1;
if (getmax(m, B) <= t) s = getmax(m, B), r = m - 1;
else l = m + 1;
}
}
if (s == -1) return -1;
int ans = 0;
for (int i = LOG - 1 ; i >= 0 ; -- i) {
if (high[s][i] <= t) {
ans += 1 << i;
s = high[s][i];
}
}
for (int i = LOG - 1 ; i >= 0 ; -- i) {
if (low[s][i] <= t) {
ans += 1 << i;
s = low[s][i];
}
}
if (s != t) return -1;
return ans;
}
