#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back
/*
yeah i could've used a set... but
i'm just coding a segtree because vibes :D
*/
struct Tree {
Tree *lt, *rt;
int l, r;
int mn1, mx1;
Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), mn1(INF(int)), mx1(NINF(int)) {};
void combine() {
mn1 = min(lt->mn1, rt->mn1);
mx1 = max(lt->mx1, rt->mx1);
}
void build(const vb& a) {
if(l == r) {
if(a[l]) {
mn1 = mx1 = l;
}
return;
}
int m = (l + r) >> 1;
lt = new Tree(l, m);
rt = new Tree(m + 1, r);
lt->build(a);
rt->build(a);
combine();
}
int qmin(int ql, int qr) {
if(ql > r || qr < l) return INF(int);
if(ql == l && qr == r) return mn1;
int m = (l + r) >> 1;
return min(lt->qmin(ql, min(qr, m)), rt->qmin(max(ql, m + 1), qr));
}
int qmax(int ql, int qr) {
if(ql > r || qr < l) return NINF(int);
if(ql == l && qr == r) return mx1;
int m = (l + r) >> 1;
return max(lt->qmax(ql, min(qr, m)), rt->qmax(max(ql, m + 1), qr));
}
void upd(int i, bool nv) {
if(l == r) {
if(nv) mn1 = mx1 = l;
else {
mn1 = INF(int);
mx1 = NINF(int);
}
return;
}
int m = (l + r) >> 1;
if(i <= m) lt->upd(i, nv);
else rt->upd(i, nv);
combine();
}
};
vi g_lptr;
vi g_rptr;
void print_vec(const vi& v) {
for(int vv : v) cerr << vv << " ";
cerr << endl;
}
void init(int N, vi H) {
vpi h_ind_pairs_right_order;
vpi h_ind_pairs_left_order;
vi lptr(N, -1);
vi rptr(N, -1);
for(int i = 0 ; i < N; i++) {
h_ind_pairs_right_order.pb({H[i], i});
h_ind_pairs_left_order.pb({H[i], i});
}
sort(h_ind_pairs_right_order.begin(), h_ind_pairs_right_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second < b.second);});
sort(h_ind_pairs_left_order.begin(), h_ind_pairs_left_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second > b.second);});
Tree tr_right(0, N - 1);
Tree tr_left(0, N - 1);
vb all_false(N, false);
tr_right.build(all_false);
tr_left.build(all_false);
for(int i = 0 ; i < N; i++) {
rptr[h_ind_pairs_right_order[i].second] = tr_right.qmin(h_ind_pairs_right_order[i].second + 1, N - 1);
lptr[h_ind_pairs_left_order[i].second] = tr_left.qmax(0, h_ind_pairs_left_order[i].second - 1);
tr_right.upd(h_ind_pairs_right_order[i].second, true);
tr_left.upd(h_ind_pairs_left_order[i].second, true);
}
g_lptr = lptr;
g_rptr = rptr;
// print_vec(lptr);
// print_vec(rptr);
}
int minimum_jumps(int A, int B, int C, int D) {
// BFS bruteforce
queue<pi> q;
int ans = -1;
for(int i = A; i <= B; i++) {
q.push({i, 0});
}
int n = g_lptr.size();
vb vis(n, false);
while(!q.empty()) {
auto [i, cd] = q.front();
q.pop();
if(i < 0 || i >= n) continue;
if(vis[i]) continue;
vis[i] = true;
if(C <= i && i <= D) {
ans = cd;
break;
}
q.push({g_lptr[i], cd + 1});
q.push({g_rptr[i], cd + 1});
}
return ans;
}
