#include "jumps.h"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
const int MAXN = 2e5+5;
constexpr int MOD = 1e9+7;
int n,m,q;
vector<array<int,2> > adj;
vector<vector<int> > lift(LGN, vector<int>());
vector<vector<int> > low(LGN, vector<int>());
vector<int> h, revh(MAXN, 0);
struct SegT {
vector<vector<int> > data;
int sz;
SegT() {}
void build(int tl, int tr, int v, vector<int> &vec) {
if(tl == tr) {
data[v].pb(vec[tl]);
return;
}
int tm = (tl + tr) >> 1;
build(tl, tm, v<<1, vec);
build(tm + 1, tr, v<<1^1, vec);
data[v].resize(tr - tl + 1);
merge(all(data[v<<1]), all(data[v<<1^1]), data[v].begin());
}
void reset(int s, vector<int> &vec) {
sz = s;
data.assign(4*(s + 3), vector<int>());
build(0, sz - 1, 1, vec);
}
array<int,2> getMax(int tl, int tr, int v, int l, int r, int x) {
if(tl >= l && tr <= r) {
auto itr = upper_bound(data[v].begin(), data[v].end(), x) - data[v].begin();
if(itr > 0) {
itr--;
return {data[v][itr], tl + itr};
}
return {-INF, sz};
}
if(tl > r || tr < l) {
return {-INF, sz};
}
int tm = (tl + tr) >> 1;
return max(getMax(tl, tm, v<<1, l, r, x), getMax(tm + 1, tr, v<<1^1, l, r, x));
}
int getMax(int l, int r, int x) {
return getMax(0, sz - 1, 1, l, r, x)[1];
}
array<int,2> getMin(int tl, int tr, int v, int l, int r, int x) {
if(tl >= l && tr <= r) {
auto itr = upper_bound(data[v].begin(), data[v].end(), x) - data[v].begin();
if(itr < data[v].size()) {
return {data[v][itr], tl + itr};
}
return {INF, sz};
}
if(tl > r || tr < l) {
return {INF, sz};
}
int tm = (tl + tr) >> 1;
return min(getMin(tl, tm, v<<1, l, r, x), getMin(tm + 1, tr, v<<1^1, l, r, x));
}
int getMin(int l, int r, int x) {
return getMin(0, sz - 1, 1, l, r, x)[1];
}
};
SegT sp;
void init(int N, std::vector<int> H) {
vector<array<int,2> > srt(N);
set<int> st;
H.pb(INF);
h = H;
n = N;
sp.reset(N, h);
for(int i = 0; i<n; i++) {
revh[h[i]] = i;
}
adj.assign(N + 5, array<int,2>({N, N}) );
adj[N] = {N, N};
REP(i, LGN) lift[i].assign(N + 5, N);
REP(i, LGN) low[i].assign(N + 5, N);
REP(i,N) {
srt[i] = {H[i], i};
st.insert(i);
}
sort(srt.begin(), srt.end());
for(auto c : srt) {
st.erase(c[1]);
auto itr = st.lower_bound(c[1]);
if(st.size() == 0) break;
if(itr != st.end()) {
adj[c[1]][1] = *itr;
}
if(itr != st.begin()) {
itr--;
adj[c[1]][0] = *itr;
}
if(H[adj[c[1]][0]] > H[adj[c[1]][1]]) {
swap(adj[c[1]][0], adj[c[1]][1]);
}
}
for(int i = 0; i<n; i++) {
lift[0][i] = adj[i][1];
low[0][i] = adj[i][0];
}
for(int k = 1; k<LGN; k++) {
for(int i = 0; i<n; i++) {
lift[k][i] = lift[k - 1][lift[k - 1][i]];
low[k][i] = low[k - 1][low[k - 1][i]];
}
}
}
int solve(int A, int C) {
if(h[A] > h[C]) return -1;
int ans = 0;
for(int i = LGN - 1; i>=0; i--) {
if(h[ lift[i][A] ] <= h[C]) {
ans += 1<<i;
A = lift[i][A];
}
}
for(int i = LGN - 1; i>=0; i--) {
if(h[ low[i][A] ] <= h[C]) {
ans += 1<<i;
A = low[i][A];
}
}
if(A != C) return -1;
return ans;
}
int minimum_jumps(int A, int B, int C, int D) {
int cmax = sp.getMax(C, D, INF);
int mx = (B + 1 > C - 1) ? h[sp.getMax(B + 1, C - 1, INF)] : -1;
if(mx > h[cmax] ) return -1;
int ab = sp.getMax(A, B, cmax);
// cout<<"cmax:" <<cmax<<" mx:"<<mx<<" ab:"<<ab<<endl;
if(ab == n) return -1;
return solve(ab, cmax);
}
