#include "jumps.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0;i<n;i++)
#define pb push_back
#define ll long long int
#define vi vector<ll>
using namespace std;
const int mxn = 200005;
int v[mxn];
int n;
vi adj[mxn];
vector<vi> l(18, vi(mxn, 1e9));
vector<vi> h(18, vi(mxn, 1e9));
const int mxn2 = 2005;
int dist[mxn2][mxn2];
int tree[mxn2][mxn2 * 4];
void upd(int dex, int pos, int num){
pos += n;
tree[dex][pos] = num;
for(pos/=2; pos >= 1; pos/=2){
tree[dex][pos] = min(tree[dex][pos * 2], tree[dex][pos * 2 + 1]);
}
}
int quer(int dex, int l, int r){
l += n; r+=n;
int ret = 1e9;
while(l <= r){
if(l % 2 == 1){
ret = min(ret, tree[dex][l++]);
}
if(r % 2 == 0){
ret = min(ret, tree[dex][r--]);
}
l/=2;
r/=2;
}
return ret;
}
void init(int N, std::vector<int> H) {
n = N;
f0r(i,N)v[i] = H[i];
int dex[n+1];
f0r(i,n){
dex[v[i]] = i;
}
stack<int>s;
f0r(i, n){
while(!s.empty() && v[s.top()] < v[i]){
s.pop();
}
if(!s.empty())adj[i].pb(s.top());
s.push(i);
}
s = stack<int>();
for(int i = n-1;i>=0;i--){
while(!s.empty() && v[s.top()] < v[i]){
s.pop();
}
if(!s.empty())adj[i].pb(s.top());
s.push(i);
}
f0r(i,n){
if(adj[i].size() == 1){
l[0][i] = adj[i][0];
h[0][i] = adj[i][0];
}
else if(adj[i].size() == 2){
if(v[adj[i][0]] > v[adj[i][1]]){
l[0][i] = adj[i][1];
h[0][i] = adj[i][0];
}
else{
h[0][i] = adj[i][1];
l[0][i] = adj[i][0];
}
}
}
for(int i = 1;i<18;i++){
f0r(j, n){
if(l[i-1][j] != 1e9)l[i][j] = l[i-1][l[i-1][j]];
if(h[i-1][j] != 1e9)h[i][j] = h[i-1][h[i-1][j]];
}
}
f0r(i, 18){
f0r(j, n){
//cout<<l[i][j]<<' ';
}
//cout<<'\n';
}
if(n <= 2000){
f0r(i, n)f0r(j,n)dist[i][j] = 1e9;
f0r(i,n){
queue<int>q;
dist[i][i] = 0;
vector<bool>vis(n, false);
vis[i] = 1;
q.push(i);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(vis[u])continue;
vis[u] = 1;
q.push(u);
dist[i][u] = min(dist[i][cur] + 1, dist[i][u]);
}
}
}
f0r(i, n){
f0r(j, n){
upd(i, j, dist[i][j]);
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(A == B && C == D){
int cur = A;
int t = D;
int ans = 0;
for(int i = 17;i>=0;i--){
if(h[i][cur] < n && v[h[i][cur]] <= v[t]){
cur = h[i][cur];
ans += (1 << i);
}
}
for(int i = 17; i>=0; i--){
if(l[i][cur] < n && v[l[i][cur]] <= v[t]){
cur = l[i][cur];
ans += (1 << i);
}
}
if(cur != t)return -1;
else return ans;
}
else if(n > 2000){
vector<bool>vis(n, 0);
vi dist(n);
queue<int>q;
for(int i = A;i<=B;i++){
dist[i] = 0;
vis[i] = 1;
q.push(i);
}
bool stop = 0;
int ans = 0;
while(!(stop || q.empty())){
int c = q.front();
q.pop();
for(auto u : adj[c]){
if(vis[u])continue;
vis[u] = 1;
dist[u] = dist[c] + 1;
q.push(u);
if(u >= C && u <= D){
ans = u;
stop = 1;
}
}
}
if(!stop)return -1;
else return dist[ans];
}
else{
int ans = 1e9;
for(int i = A; i<=B;i++){
ans = min(ans, quer(i, C, D));
}
if(ans == 1e9)return -1;
else return ans;
}
}
