#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#include <cassert>
#include "jumps.h"
#define SZ(x) (LL)(x.size())
#define FR(i,a,b) for(LL i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
typedef std::pair<LD,LD> PLD;
using namespace std;
const int MAXN=2e5+5, MAXLG=20;
int h[MAXN];
int l[MAXN], r[MAXN];
int hp[MAXN][MAXLG], rp[MAXN][MAXLG]; //high par, right par
int n;
/*
7 3
3 2 1 6 4 5 7
4 4 6 6
*/
void init(int N, std::vector<int> H) {
n=N;
FOR(i,n) h[i]=H[i];
deque<int> dq;
FOR(i,n){
while (!dq.empty () && h[dq.back()]<h[i]) dq.pop_back();
if (dq.empty()) l[i]=-1;
else l[i]=dq.back();
dq.push_back(i);
}
dq.clear();
for(int i=n-1;i>=0;i--){
while (!dq.empty () && h[dq.back()]<h[i]) dq.pop_back();
if (dq.empty()) r[i]=-1;
else r[i]=dq.back();
dq.push_back(i);
}
FOR(i,n){
if (l[i]==-1 && r[i]==-1) hp[i][0]=rp[i][0]=-1;
else if (r[i]==-1){
hp[i][0]=l[i];
rp[i][0]=-1;
}
else if (l[i]==-1) hp[i][0]=rp[i][0]=r[i];
else{
rp[i][0]=r[i];
if (h[l[i]]>h[r[i]]) hp[i][0]=l[i];
else hp[i][0]=r[i];
}
}
FR(j,1,MAXLG) FOR(i,n){
int p=rp[i][j-1];
if (p!=-1) rp[i][j]=rp[p][j-1];
else rp[i][j]=-1;
p=hp[i][j-1];
if (p!=-1) hp[i][j]=hp[p][j-1];
else hp[i][j]=-1;
}
//FOR(i,n) cout<<hp[i][1]<<" "<<rp[i][1]<<"\n";
}
int minimum_jumps(int a, int b, int c, int d) {
int mx=h[c], cur=a, ans=0;
for (int j=MAXLG-1; j>=0; j--){
if (hp[cur][j]!=-1 && h[hp[cur][j]]<=mx){
cur=hp[cur][j];
ans+=(1<<j);
}
}
if (h[cur]==mx) return ans;
for (int j=MAXLG-1; j>=0; j--){
if (rp[cur][j]!=-1 && h[rp[cur][j]]<=mx){
cur=rp[cur][j];
ans+=(1<<j);
}
}
if (h[cur]==mx) return ans;
return -1;
}
