#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#include "jumps.h"
using namespace std;
set<pair<int, int>> lf, rg;
vector<int> g[200005];
int n;
int mx[4 * 200005], mn[4 * 200005];
void up(int l, int r, int ind, int num, int v){
if(l > ind || r < ind) return;
if(l == r){
mx[v] = num;
return;
}
int mid = (l + r) / 2;
up(l, mid, ind, num, v * 2);
up(mid + 1, r, ind, num, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
int get_mx(int l, int r, int l1, int r1, int v){
if(l > r1 || l1 > r) return 0;
if(l >= l1 && r1 >= r) return mx[v];
int mid = (l + r) / 2;
return min(get_mx(l, mid, l1, r1, v * 2), get_mx(mid + 1, r, l1, r1, v * 2 + 1));
}
void init(int N, std::vector<int> H) {
n = N;
for(int i = 0; i < N; i++) up(1, n, i + 1, H[i], 1);
for(int i = 1; i <= n; i++){
int L = 0, R = i;
while(L + 1 < R){
int mid = (L + R) / 2;
if(get_mx(1, n, mid, i, 1) > H[i - 1]) L = mid;
else R = mid;
}
if(L != 0) g[i].push_back(L);
L = i, R = n + 1;
while(L + 1 < R){
int mid = (L + R) / 2;
if(get_mx(1, n, i, mid, 1) > H[i - 1]) R = mid;
else L = mid;
}
if(R != n + 1) g[i].push_back(R);
}
}
int dist[200005];
bool us[200005];
int minimum_jumps(int A, int B, int C, int D) {
A++;
B++;
C++;
D++;
for(int i = 1; i <= n; i++){
us[i] = 0;
dist[i] = 0;
}
deque<int> d;
for(int i = A; i <= B; i++){
d.push_back(i);
us[i] = 1;
}
int mn = 2e9;
while(!d.empty()){
int num = d.front();
if(num >= C && num <= D) mn = min(mn, dist[num]);
d.pop_front();
for(int to : g[num]){
if(!us[to]){
us[to] = 1;
dist[to] = dist[num] + 1;
d.push_back(to);
}
}
}
if(mn == 2e9) return -1;
else return mn;
}
