#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int n, a[MAXN], l_max[MAXN], r_max[MAXN];
int anc_l[20][MAXN], anc_r[20][MAXN], anc_max[20][MAXN];
void init(int N, vector<int> H) {
n = N;
for(int i = 1; i <= N; i++) a[i] = H[i-1];
a[0] = a[N+1] = N+1;
anc_r[0][N+1] = N+1;
for(int i = 1; i <= N; i++) {
l_max[i] = i-1;
while(a[l_max[i]] < a[i]) l_max[i] = l_max[l_max[i]];
anc_l[0][i] = l_max[i];
}
for(int i = N; i >= 1; i--) {
r_max[i] = i+1;
while(a[r_max[i]] < a[i]) r_max[i] = r_max[r_max[i]];
anc_r[0][i] = r_max[i];
if(a[l_max[i]] > a[r_max[i]]) anc_max[0][i] = l_max[i];
else anc_max[0][i] = r_max[i];
}
for(int bit = 1; bit < 20; bit++) {
for(int i = 0; i <= N+1; i++) {
anc_l[bit][i] = anc_l[bit-1][anc_l[bit-1][i]];
anc_r[bit][i] = anc_r[bit-1][anc_r[bit-1][i]];
anc_max[bit][i] = anc_max[bit-1][anc_max[bit-1][i]];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++; B++; C++; D++;
// Estamos lidando apenas com os casos onde C = D
// Daí, primeiro achamos em qual x iremos trabalhar
int x = max(l_max[C] + 1, A);
if(x > B) return -1;
// Fazer binary lifting até achar o maior valor pra direita
for(int bit = 19; bit >= 0; bit--)
if(anc_r[bit][x] <= B) x = anc_r[bit][x];
// x é o valor que iremos partir para achar a resposta
// seguimos o maior valor até se tornar maior que a[C]
int ans = 0;
for(int bit = 19; bit >= 0; bit--)
if(a[anc_max[bit][x]] <= a[C]) x = anc_max[bit][x], ans += (1 << bit);
// depois seguimos indo sempre para a direita
for(int bit = 19; bit >= 0; bit--)
if(a[anc_r[bit][x]] <= a[C]) x = anc_r[bit][x], ans += (1 << bit);
return ans;
}
