#include "jumps.h"
// all the includes you need here
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <bitset>
#include <deque>
#include <iomanip>
#include <numeric>
#include <functional>
#include <complex>
#include <random>
#include <chrono>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<ld, ld> pld;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<pld> vpld;
typedef vector<string> vs;
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define rrep(i, a, b) for (int i = (b) - 1; i >= a; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define trav(a, x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define pq priority_queue
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl;
#define debug2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define debug3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define debug4(x, y, z, w) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << endl;
#define debug5(x, y, z, w, t) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << endl;
#define debug6(x, y, z, w, t, u) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << endl;
#define debug7(x, y, z, w, t, u, v) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << endl;
#define debug8(x, y, z, w, t, u, v, k) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << ", " << #k << " = " << k << endl;
#define debug9(x, y, z, w, t, u, v, k, l) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << ", " << #k << " = " << k << ", " << #l << " = " << l << endl;
const int N = 1e5 + 5;
const int LG = 22;
ll n;
vii a;
int lft[N], rgt[N];
// high[i] = the index of max(lft[i], rgh[i]), low[i] = the index of min(lft[i], rgh[i])
int high[N], low[N];
// uph[i][j] = high[high[...[i]]] (2^j times), upl[i][j] = low[low[...[i]]] (2^j times)
int uph[N][LG], upl[N][LG];
// a function to find for each index i, the greatest index j such that j <= i and a[j] > a[i]
void find_left() {
stack<int> st;
rep(i, 0, n) {
while (!st.empty() && a[st.top()] <= a[i]) {
st.pop();
}
if (st.empty()) {
lft[i] = -1;
} else {
lft[i] = st.top();
}
st.push(i);
}
}
// a function to find for each index i, the smallest index j such that j >= i and a[j] > a[i]
void find_right() {
stack<int> st;
rrep(i, 0, n) {
while (!st.empty() && a[st.top()] <= a[i]) {
st.pop();
}
if (st.empty()) {
rgt[i] = n;
} else {
rgt[i] = st.top();
}
st.push(i);
}
}
// a function to calculate the high and low arrays
void calc_high_low() {
rep(i, 0, n) {
if (lft[i] == -1 && rgt[i] == n) {
high[i] = -1;
low[i] = -1;
} else if (lft[i] == -1) {
high[i] = rgt[i];
low[i] = rgt[i];
} else if (rgt[i] == n) {
high[i] = lft[i];
low[i] = lft[i];
} else {
if (a[lft[i]] > a[rgt[i]]) {
high[i] = lft[i];
low[i] = rgt[i];
} else {
high[i] = rgt[i];
low[i] = lft[i];
}
}
}
}
// a function to calculate the sparse table for high and low
void calc_sparse() {
rep(i, 0, n) {
uph[i][0] = high[i];
upl[i][0] = low[i];
}
rep(j, 1, LG) {
rep(i, 0, n) {
if (uph[i][j - 1] == -1) {
uph[i][j] = -1;
} else {
uph[i][j] = uph[uph[i][j - 1]][j - 1];
}
if (upl[i][j - 1] == -1) {
upl[i][j] = -1;
} else {
upl[i][j] = upl[upl[i][j - 1]][j - 1];
}
}
}
}
// a function to go up from an index i by moving on the high array until we reach an index j such that a[j] > x
int go_up_high(int i, int x, int& cnt) {
//cout<<"CALLED: "<<i<<" "<<x<<endl;
if (i == -1) {
return -1;
}
if (a[i] > x) {
return -1;
}
if(a[i]==x){
return i;
}
rrep(j, 0, LG - 1) {
if (uph[i][j] == -1) {
continue;
}
if (a[uph[i][j]] <= x) {
i = uph[i][j];
cnt += (1 << j);
}
}
return i;
}
// a function to go up from an index i by moving on the low array until we reach an index j such that a[j] > x
int go_up_low(int i, int x, int& cnt) {
if (i == -1) {
return -1;
}
if (a[i] > x) {
return -1;
}
if(a[i]==x){
return i;
}
rrep(j, 0, LG - 1) {
if (upl[i][j] == -1) {
continue;
}
if (a[upl[i][j]] <= x) {
i = upl[i][j];
cnt += (1 << j);
}
}
return i;
}
void init(int N, std::vector<int> H) {
n = N;
a = H;
find_left();
find_right();
calc_high_low();
calc_sparse();
}
int minimum_jumps(int A, int B, int C, int D) {
if(A==B && C==D){
if(B==C){
return 0;
}
int cnt=0;
int x = go_up_high(B, a[C], cnt);
int y = go_up_low(x, a[C], cnt);
// debug2(x, y);
// debug(cnt);
// for(int i=0;i<n;i++){
// debug6(i, a[i], lft[i], rgt[i], high[i], low[i]);
// }
// // debug the uph and upl arrays
// rep(i, 0, n) {
// rep(j, 0, LG) {
// debug3(i, j, uph[i][j]);
// }
// }
if(a[y]==a[C]){
return cnt;
}
return -1;
}
return -1;
}
