#include <cassert>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include "jumps.h"
using namespace std;
vector<vector<int>> adj;
bool subtask1 = true;
const int maxk = 20;
const int maxn = 2e5;
int L[maxn][maxk];
int R[maxn][maxk];
int tree[maxn * 4];
vector<int> H;
void build(int id, int tl, int tr, vector<int> &h) {
if(tl == tr) {
tree[id] = h[tl];
return;
}
int tm = (tl + tr) / 2;
build(id * 2 + 1, tl, tm, h);
build(id * 2 + 2, tm + 1, tr, h);
tree[id] = max(tree[id * 2 + 1], tree[id * 2 + 2]);
}
int query(int id, int tl, int tr, int l, int r) {
if(tl == l && r == tr) return tree[id];
int tm = (tl + tr) / 2;
if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);
int LQ = query(id * 2 + 1, tl, tm, l, tm);
int RQ = query(id * 2 + 2, tm + 1, tr, tm + 1, r);
return max(LQ, RQ);
}
void init(int n, vector<int> h) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < maxk; j++) {
L[i][j] = n;
R[i][j] = -1;
}
}
vector<int> q;
for (int i = 0; i < n; ++i) {
if (h[i] != i + 1) subtask1 = false;
while (!q.empty() && h[q.back()] < h[i]) {
q.pop_back();
}
if (!q.empty()) {
L[i][0] = q.back();
}
q.push_back(i);
}
q.clear();
for (int i = n - 1; i >= 0; --i) {
while (!q.empty() && h[q.back()] < h[i]) {
q.pop_back();
}
if (!q.empty()) {
R[i][0] = q.back();
}
q.push_back(i);
}
for (int j = 1; j < maxk; j++) {
for (int i = 0; i < n; i++) {
int u = L[i][j - 1];
int v = R[i][j - 1];
R[i][j] = max(R[u][j - 1], R[v][j - 1]);
L[i][j] = min(L[u][j - 1], L[v][j - 1]);
}
}
build(0, 0, n - 1, h);
H = h;
}
int minimum_jumps(int A, int B, int C, int D) {
int n = adj.size();
if (A == B && C == D) {
int res = 0;
int r = A, l = A;
for (int j = maxk - 1; j >= 0; j--) {
if (R[r][j] != -1 && R[r][j] < C) {
r = R[r][j];
res += (1 << j);
l = L[l][j];
}
}
if (R[r][0] == C) return res + 1;
if (l != n && R[l][0] == C) return res + 1;
if(A + 1 == C) return -1;
int h = query(0, 0, n - 1, A + 1, C - 1);
if(h > H[C]) return -1;
return res + 1;
}
return -1;
}
