#include<bits/stdc++.h>
#include "jumps.h"
#define fr first
#define sc second
using namespace std;
const int N = 200010;
const int LOGN = 20;
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;
struct Segtree2{
pair <int, int> tree[4*N];
pair <int, int> join(pair <int, int> a, pair <int, int> b){
if(a.fr > b.fr) return a;
return b;
}
void build(int node, int l, int r){
if(l == r){
tree[node] = {0, l};
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] = {val, 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 {-1, -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));
}
} seg2;
int l[N], r[N];
int lc[N], rc[N];
int pai[N][LOGN], pai2[N][LOGN];
int tin[N], tout[N];
vector <int> g[N];
int n;
int tmm;
int il[N], ir[N];
int alt[N];
void dfs(int v, int p){
pai2[v][0] = p;
tin[v] = tmm;
tmm++;
for(auto x : g[v]){
if(x == p) continue;
alt[x] = alt[v]+1;
dfs(x, v);
}
tout[v] = tmm;
tmm++;
}
void construct(int l = 1, int r = n){
int t = seg2.query(1, l, r, 1, n).sc;
il[t] = l;
ir[t] = r;
if(seg2.query(1, l, t-1, 1, n).first > 0){
lc[t] = seg2.query(1, l, t-1, 1, n).sc;
construct(l, t-1);
}
if(seg2.query(1, t+1, r, 1, n).fr > 0){
rc[t] = seg2.query(1, t+1, r, 1, n).sc;
construct(t+1, r);
}
}
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);
}
reverse(v.begin(), v.end());
seg2.build(1, 1, n);
for(auto [val, pos] : v){
lc[pos] = rc[pos] = -1;
seg2.update(1, 1, n, pos, val);
}
construct();
int raiz = 0;
for(int i = 1;i <= n;i++){
if(h[i-1] == n) raiz = i;
if(lc[i] != -1){
g[lc[i]].push_back(i);
g[i].push_back(lc[i]);
}
if(rc[i] != -1) {
g[rc[i]].push_back(i);
g[i].push_back(rc[i]);
}
//cout << lc[i] << ' ' << rc[i] << '\n';
}
tmm = 1;
g[raiz].push_back(0);
g[0].push_back(raiz);
pai[raiz][0] = 0;
pai2[raiz][0] = 0;
dfs(0, 0);
for(int i = 1;i <= n;i++){
if(l[i] == -1 and r[i] == -1) {
continue;
}
if(l[i] == -1) pai[i][0] = r[i];
else if(r[i] == -1) pai[i][0] = l[i];
else{
int u = l[i], v = r[i];
if(tin[u] <= tin[v] and tout[v] <= tout[u]){
pai[i][0] = u;
}
else{
pai[i][0] = v;
}
}
}
for(int bit = 1;bit < LOGN;bit++){
for(int i = 1;i <= n;i++){
pai[i][bit] = pai[pai[i][bit-1]][bit-1];
pai2[i][bit] = pai2[pai2[i][bit-1]][bit-1];
}
}
return;
}
int check(int u, int v){
return (tin[v] <= tin[u] and tout[u] <= tout[v]);
}
vector <int> choose(int a, int b, int c){
a = max(a, il[c]);
vector <int> ans;
while(a <= b){
int t = seg2.query(1, a,b, 1, n).sc;
ans.push_back(t);
a = ir[t]+1;
}
return ans;
}
int minimum_jumps(int a, int b, int c, int d) {
// a=b and c = d
a++;
b++;
c++;
d++;
int big = seg2.query(1, c, d, 1, n).sc;
vector <int> st = choose(a, b, big);
//cout << big << '\n';
int resp = 1e9;
for(auto u : st){
int v = c;
//cout << u << ' ';
if(!check(u, big)){
continue;
}
int res = 0;
for(int bit = LOGN-1;bit >= 0;bit--){
if(u >= c) break;
if(check(pai[u][bit], big)){
u = pai[u][bit];
int t = (1<<bit);
res += t;
}
}
for(int bit = LOGN-1;bit >= 0;bit--){
if(u >= c) break;
if(check(pai2[u][bit], big)){
u = pai2[u][bit];
int t = (1<<bit);
res += t;
}
}
resp = min(res, resp);
}
return (resp == 1e9 ? -1 : resp);
}
