#include <bits/stdc++.h>
using namespace std;
#include "jumps.h"
int n; vector<int> A,B,C,D;
array<int,18> id;
vector<array<int,18>> jump,force;
vector<int> segtree;
void init(int N,vector<int> H){
for (int& a:H) --a;
H.emplace_back(-1);
n = N,A = H;
D.resize(n);
for (int i(0);i < n;++i) D[A[i]] = i;
fill(id.begin(),id.end(),n);
jump.assign(n+1,id),force.assign(n+1,id);
segtree.assign(2*n,-1);
B.resize(n),C.resize(n);
for (int i(0);i < n;++i){
int res = -1;
for (int l(n+A[i]),r(n+n);l < r;l>>=1,r>>=1){
if (l&1) res = max(res,segtree[l++]);
if (r&1) res = max(res,segtree[--r]);
}
B[i] = (res==-1?n:res);
for (int l(n+A[i]);l;l>>=1) segtree[l] = i;
}
segtree.assign(2*n,n);
for (int i(n-1);i > -1;--i){
int res = n;
for (int l(n+A[i]),r(n+n);l < r;l>>=1,r>>=1){
if (l&1) res = min(res,segtree[l++]);
if (r&1) res = min(res,segtree[--r]);
}
C[i] = res;
if (A[res]>A[B[i]]) B[i] = res;
for (int l(n+A[i]);l;l>>=1) segtree[l] = i;
}
copy(A.begin(),A.end()-1,segtree.begin()+n);
for (int i(n-1);i;--i) segtree[i] = max(segtree[i<<1],segtree[i<<1|1]);
for (int i(0);i < n;++i) jump[i][0] = B[i],force[i][0] = C[i];
for (int k(1);k < 18;++k) for (int i(0);i < n;++i){
jump[i][k] = jump[jump[i][k-1]][k-1],force[i][k] = force[force[i][k-1]][k-1];
}
A[n] = n;
}
int minimum_jumps(int a,int b,int c,int d){
++b,++d;
int x = -1,y = -1;
for (int l(n+b),r(n+c);l < r;l>>=1,r>>=1){
if (l&1) x = max(x,segtree[l++]);
if (r&1) x = max(x,segtree[--r]);
}
for (int l(n+c),r(n+d);l < r;l>>=1,r>>=1){
if (l&1) y = max(y,segtree[l++]);
if (r&1) y = max(y,segtree[--r]);
}
if (x>y) return -1;
int s = -1,res = 0;
vector<int> T,U;
for (int l(n+a),r(n+b);l < r;l>>=1,r>>=1){
if (l&1) U.emplace_back(l++);
if (r&1) T.emplace_back(--r);
}
copy(U.rbegin(),U.rend(),back_inserter(T));
for (int i:T) if (segtree[i]>y){
while(i<n){
i = i<<1|1;
if (segtree[i]<y) s = max(s,segtree[i]),i ^= 1;
}
break;
} else s = max(s,segtree[i]);
if (s==-1) return -1;
s = D[s];
for (int i(17);i > -1;--i) if (A[jump[s][i]]<x) res += (1<<i),s = jump[s][i];
if (A[jump[s][0]]<y&&A[s]<x) ++res,s = jump[s][0];
for (int i(17);i > -1;--i) if (force[s][i]<c) res += (1<<i),s = force[s][i];
return res+(s<c);
}
