#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> seg,br,d;ll n;
ll qw(ll a,ll b){
ll ans=0;
for (a+=n,b+=n;a<b;a/=2,b/=2){
if (a%2){
ans=max(ans,seg[a]);
a++;
}
if (b%2){
b--;
ans=max(ans,seg[b]);
}
}
return ans;
}
ll ind(ll v,ll a,ll b){
if (a==b){
return a;
}
ll m=(a+b)/2;
if (qw(a,m)>=v){
return ind(v,a,m);
}
return ind(v,m+1,b);
}
/*#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n; cin >> n;
vector<ll> a(n), r(n);
for (ll i = 0; i < n; i++) {
cin >> a[i];
r[i] = i - 1;
}
for (ll i = 0; i < n; i++) {
ll j = i;
while (r[j] != -1) {
if (a[i] > a[r[j]]) {
break;
}
j = r[j];
}
r[i] = r[j];
cout << r[i] + 1 << '\n';
}
}*/
void init(int N, std::vector<int> H) {
n=N;
seg=vector<ll>(2*n,0);
//segment setup
for (ll i=0;i<n;i++){
seg[i+n]=H[i];
}
for (ll i=n;i>0;i--){
seg[i]=max(seg[2*i],seg[2*i+1]);
}
//br setup
br=vector<ll>(n,0);for (ll i=0;i<n;i++){br[i]=i+1;}
for (ll i = n-1; i >= 0; i--) {
ll j = i;
while (br[j] != n) {
if (H[i] < H[br[j]]) {
break;
}
j = br[j];
}
br[i] = br[j];
}
//distance
d=vector<ll>(n+1);d[n]=0;
for (ll i=0;i<n;i++){
d[i]=d[br[i]]+1;
}
}
//ind,qw,d
int minimum_jumps(int A, int B, int C, int D) {
ll x=ind(seg[B+n],seg[C+n],seg[D+n]);
if (d[B]>d[x]){
return d[B]-d[x];
}
return -1;
}
