#include <bits/stdc++.h>
using namespace std;
struct direction {
int gauche, droite;
};
int N;
vector<int> hauteurs;
vector<vector<direction>> plusCourt;
int minimum_jumps(int A, int B, int C, int D) {
int result = 0;
A++; B++; C++; D++;
if (A < C) {
int bitAct = 17;
while (bitAct >= 0) {
while (plusCourt[A][bitAct].droite == 0 || plusCourt[A][bitAct].droite > hauteurs[C-1]) {
bitAct--;
}
if (bitAct >= 0) {
A = plusCourt[A][bitAct].droite;
result += (1 << bitAct);
}
}
}
else {
int bitAct = 17;
while (bitAct >= 0) {
while (plusCourt[A][bitAct].gauche == 0 || plusCourt[A][bitAct].gauche > hauteurs[C-1]) {
bitAct--;
}
if (bitAct >= 0) {
A = plusCourt[A][bitAct].gauche;
result += (1 << bitAct);
}
}
}
if (A != C) return -1;
return result;
}
void init(int _N, vector<int> H) {
ios::sync_with_stdio(false);
cin.tie(0);
N = _N;
hauteurs.resize(N);
for (int i = 0; i < N; i++) {
hauteurs[i] = H[i];
}
plusCourt.resize(N+1, vector<direction>(18, {0, 0}));
vector<direction> parents(N+1, {0, 0});
vector<pair<int, int>> parentDroite;
parentDroite.push_back({hauteurs[0], 0});
for (int i = 1; i < N; i++) {
while (!parentDroite.empty() && hauteurs[i] > parentDroite.back().first) {
parents[parentDroite.back().second+1].droite = i+1;
cout << parentDroite.back().second+1 << " -> " << i+1 << '\n';
parentDroite.pop_back();
}
parentDroite.push_back({hauteurs[i], i});
}
vector<pair<int, int>> parentGauche;
parentGauche.push_back({hauteurs[N-1], N-1});
for (int i = N-2; i >= 0; i--) {
while (!parentGauche.empty() && hauteurs[i] > parentGauche.back().first) {
parents[parentGauche.back().second+1].gauche = i+1;
cout << parentGauche.back().second+1 << " -> " << i+1 << '\n';
parentGauche.pop_back();
}
parentGauche.push_back({hauteurs[i], i});
}
for (int iNoeud = 1; iNoeud <= N; iNoeud++) {
plusCourt[iNoeud][0] = {parents[iNoeud].gauche, parents[iNoeud].droite};
}
for (int iBit = 1; iBit < 18; iBit++) {
for (int iNoeud = 1; iNoeud <= N; iNoeud++) {
plusCourt[iNoeud][iBit].gauche = max(plusCourt[plusCourt[iNoeud][iBit-1].gauche][iBit-1].gauche,
plusCourt[plusCourt[iNoeud][iBit-1].droite][iBit-1].gauche);
plusCourt[iNoeud][iBit].droite = max(plusCourt[plusCourt[iNoeud][iBit-1].gauche][iBit-1].droite,
plusCourt[plusCourt[iNoeud][iBit-1].droite][iBit-1].droite);
}
}
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int Q;
// cin >> N >> Q;
// int* H_array = new int[N];
// for (int i = 0; i < N; i++) cin >> H_array[i];
// init(N, H_array);
// for (int i = 0; i < Q; i++) {
// int A, B, C, D;
// cin >> A >> B >> C >> D;
// cout << minimum_jumps(A, B, C, D) << "\n";
// }
// delete[] H_array;
// return 0;
// }
