#include<bits/stdc++.h>
#include "jumps.h"
#define fr first
#define sc second
using namespace std;
const int N = 200010;
struct Segtree{
pair <int, int> tree[4*N];
pair <int, int> join(pair <int, int> a, pair <int, int> b){
return {min(a.fr, b.fr), max(a.sc, b.sc)};
}
void build(int node, int l, int r){
if(l == r){
tree[node] = {1e9, 0};
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void update(int node, int l, int r, int pos, int val){
if(l == r){
tree[node] = {l, l};
return;
}
int mid = (l+r)/2;
if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node+1, mid+1, r, pos, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r) return {1e9, -1};
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg;
int l[N], r[N];
int n;
void init(int N, vector<int> h) {
n = N;
vector <pair <int, int>> v;
for(int i = 0;i < n;i++){
v.push_back({h[i], i+1});
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
seg.build(1, 1, n);
for(auto [val, pos] : v){
l[pos] = r[pos] = -1;
if(seg.query(1, 1, pos-1, 1, n).sc > 0) l[pos] = seg.query(1, 1, pos-1, 1, n).sc;
if(seg.query(1, pos+1, n, 1, n).fr < 1e9) r[pos] = seg.query(1, pos+1, n, 1, n).fr;
seg.update(1,1, n, pos, pos);
}
}
int dist[N];
int minimum_jumps(int a, int b, int c, int d) {
queue <int> q;
a++;
b++;
c++;
d++;
for(int i = 1;i <= n;i++){
dist[i] = -1;
}
for(int i = a;i <= b;i++){
dist[i] = 0;
q.push(i);
}
while(!q.empty()){
int v = q.front();
q.pop();
if(l[v] != -1){
if(dist[l[v]] == -1){
dist[l[v]] = dist[v]+1;
q.push(l[v]);
}
}
if(r[v] != -1){
if(dist[r[v]] == -1){
dist[r[v]] = dist[v]+1;
q.push(r[v]);
}
}
}
int res = 1e8;
for(int i = c;i <= d;i++){
if(dist[i] == -1) continue;
res = min(res, dist[i]);
}
return (res == 1e8 ? -1 : res);
}
