#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include "jumps.h"
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z){
for (const T& x : Z)
cout << x << ' ';
cout << "\n";
}
void printVariable(const any& var) {
if (!var.has_value()) {
cout << "null";
return;
}
if (var.type() == typeid(int)) {
cout << any_cast<int>(var);
} else if (var.type() == typeid(double)) {
cout << any_cast<double>(var);
} else if (var.type() == typeid(float)) {
cout << any_cast<float>(var);
} else if (var.type() == typeid(char)) {
cout << any_cast<char>(var);
} else if (var.type() == typeid(bool)) {
cout << (any_cast<bool>(var) ? "true" : "false");
} else if (var.type() == typeid(string)) {
cout << any_cast<string>(var);
} else if (var.type() == typeid(const char*)) {
cout << any_cast<const char*>(var);
} else if (var.type() == typeid(long long)) {
cout << any_cast<long long>(var);
} else {
cout << "[unknown type]";
}
}
template<typename... Args>
void outval(Args... args) {
vector<any> variables = {args...};
for (size_t i = 0; i < variables.size(); ++i) {
printVariable(variables[i]);
if (i != variables.size() - 1) {
cout << " ";
}
}
cout << "\n";
}
#define sp << " " <<
/********* DEBUG *********/
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll inf = 1e18;
const ll mxN = 2000005;
vector<ll> heights(mxN);
ll n;
vector<ll> pref(mxN), suff(mxN);
const ll LOGN = 22;
ll jumpR[mxN][LOGN], jumpL[mxN][LOGN];
ll realJump[mxN][LOGN];
void init(int N, vector<int> H) {
n=N;
heights.resize(n);
pref.resize(n);
suff.resize(n);
for (int i = 0; i < n; i++)
heights[i] = H[i];
// [height, idx]
stack<pair<ll, ll>> st;
for (int i = 0; i < n; i++){
while (st.size() && st.top().first < heights[i])
st.pop();
if (st.empty())
pref[i] = -1;
else
pref[i] = st.top().second;
st.push({heights[i], i});
}
while(st.size())
st.pop();
for (int i = n-1; i >= 0; i--){
while (st.size() && st.top().first < heights[i])
st.pop();
if (st.empty())
suff[i] = -1;
else
suff[i] = st.top().second;
st.push({heights[i], i});
}
// outvec(pref);
// outvec(suff);
for (int i = 0; i < LOGN; i++){
for (int j = 0; j < n; j++){
if (i == 0)
jumpR[j][i] = suff[j];
else if (jumpR[j][i-1] != -1)
jumpR[j][i] = jumpR[ jumpR[j][i-1] ][ i-1 ];
else
jumpR[j][i] = -1;
}
}
for (int i = 0; i < LOGN; i++){
for (int j = n-1; j >= 0; j--){
if (i == 0)
jumpL[j][i] = pref[j];
else if (jumpL[j][i-1] != -1)
jumpL[j][i] = jumpL[ jumpL[j][i-1] ][ i-1 ];
else
jumpL[j][i-1] = -1;
}
}
for (int i = 0; i < LOGN; i++){
for (int j = 0; j < n; j++){
if (i == 0){
if (suff[j] == -1 && pref[j] == -1)
realJump[j][i] = -1;
if (suff[j] == -1)
realJump[j][i] = pref[j];
else if (pref[j] == -1)
realJump[j][i] = suff[j];
else
realJump[j][i] = heights[suff[j]] > heights[pref[j]] ? suff[j] : pref[j];
}
else if (realJump[j][i-1] != -1)
realJump[j][i] = realJump[ realJump[j][i-1] ][ i-1 ];
else
realJump[j][i] = -1;
}
}
}
ll binpow(ll a, ll b, ll m){
a %= m;
ll ans = 1;
while (b){
if (b & 1)
ans = (ans * a) % m;
a = (a * a) % m;
b >>= 1;
}
return ans;
}
// subtask 5
int minimum_jumps(int A, int B, int C, int D) {
int curr = A, moves = 0;
for (int i = LOGN-1; i >= 0; i--){
if (realJump[curr][i] == -1)
continue;
if (heights[ realJump[curr][i] ] <= heights[C]){
curr = realJump[curr][i];
moves += binpow(2, i, 1e10);
}
}
for (int i = LOGN-1; i >= 0; i--){
if (jumpR[curr][i] == -1)
continue;
if (heights[ jumpR[curr][i] ] <= heights[C]){
curr = jumpR[curr][i];
moves += binpow(2, i, 1e10);
if (curr == C)
break;
}
}
return moves;
}
