#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back
const int maxn = 2e5 + 10, INF = 1e9 + 7;
int n, h[maxn], tree[maxn * 4], jump[maxn][20];
void build(int tl = 0, int tr = maxn, int i = 1){
if (tl == tr){
tree[i] = tl; return;
}
int tm = (tl + tr) / 2;
build(tl, tm, i * 2); build(tm + 1, tr, i * 2 + 1);
tree[i] = (h[tree[i * 2]] < h[tree[i * 2 + 1]] ?
tree[i * 2] : tree[i * 2 + 1]);
}
int solve(int s, int e){
int re = 0;
for (int p = 19; p >= 0; p--){
if (jump[s][p] < e) re += (1<<p), s = jump[s][p];
}
re++; s = jump[s][0];
if (s == e) return re;
return INF;
}
void init(int N, vector<int> H){
fill(h, h + maxn, INF);
n = N;
FOR(i, n) h[i] = H[i];
build();
stack<int> s;
for (int i = n - 1; i >= 0; i--){
while (!s.empty() && h[s.top()] < h[i]) s.pop();
jump[i][0] = (s.empty() ? i : s.top());
s.push(i);
}
for (int p = 1; p < 20; p++){
FOR(i, n) jump[i][p] = jump[jump[i][p - 1]][p - 1];
}
}
int minimum_jumps(int a, int b, int c, int d){
int re = INF;
for (int i = a; i <= b; i++){
for (int j = c; j <= d; j++){
re = min(re, solve(i, j));
}
}
return (re != INF ? re : -1);
}
