#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, l[202020], r[202020], par[202020], sx[202020], rt, dh[202020], pf[202020][20];
array<ll, 2> seg[808080];
vector<int> h;
void dfs(ll x, ll f, ll t) {
if (x < 0)
return;
par[x] = f;
pf[x][0] = par[sx[x]];
dh[l[x]] = dh[r[x]] = dh[x] + 1;
sx[l[x]] = t ? x : sx[x];
sx[r[x]] = t ? sx[x] : x;
dfs(l[x], x, 0), dfs(r[x], x, 1);
}
void ini(ll s, ll e, ll d) {
if (s < e)
ini(s, s + e >> 1, d * 2), ini(s + e + 2 >> 1, e, d * 2 + 1), seg[d] = max(seg[d * 2], seg[d * 2 + 1]);
else
seg[d] = {h[s], s};
}
array<ll, 2> fnd(ll l, ll r, ll s = 0, ll e = n - 1, ll d = 1) {
if (s > r || e < l)
return {0, 0};
if (s >= l && e <= r)
return seg[d];
return max(fnd(l, r, s, s + e >> 1, d * 2), fnd(l, r, s + e + 2 >> 1, e, d * 2 + 1));
}
ll dnc(ll s, ll e) {
if (s > e)
return -1;
ll t = fnd(s, e)[1];
l[t] = dnc(s, t - 1), r[t] = dnc(t + 1, e);
return t;
}
void init(int N, vector<int> H) {
assert(N <= 200);
h = H;
n = N;
ini(0, n - 1, 1);
rt = dnc(0, n - 1);
sx[rt] = n, dh[n] = -1, par[n] = n, dfs(rt, n, 0);
for (int k = 1; k < 20; k++) {
pf[n][k - 1] = n;
for (int i = 0; i < n; i++)
pf[i][k] = pf[pf[i][k - 1]][k - 1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
ll bl = fnd(B + 1, C - 1)[0], od = D;
D = fnd(C, D)[1];
if (bl > h[D])
return -1;
for (; A <= B;) {
A = fnd(A, B)[1];
if (h[A] < h[D])
break;
A++;
}
if (A > B)
return -1;
for (; C < D;) {
ll pt = fnd(C, D - 1)[1];
if (h[pt] < max<ll>(h[A], bl))
break;
D = pt;
}
ll rs = 0, x = A;
for (int k = 20; k--;)
if (dh[pf[x][k]] >= dh[D])
x = pf[x][k], rs += 1 << k;
ll res = rs + dh[x] - dh[D];
/*for (int k = 2; k < 400; k += 2) {
x = pf[x][0];
if (x >= C && x <= od)
res = min(res, rs + k - 1);
if (par[x] >= C && par[x] <= od)
res = min(res, rs + k);
}*/
for (; A < B;) {
A = fnd(A + 1, B)[1];
for (; C < D;) {
ll pt = fnd(C, D - 1)[1];
if (h[pt] < max<ll>(h[A], bl))
break;
D = pt;
}
ll rs = 0, x = A;
for (int k = 20; k--;)
if (dh[pf[x][k]] >= dh[D])
x = pf[x][k], rs += 1 << k;
assert(res <= rs + dh[x] - dh[D]);
}
return res;
}
