#include <bits/stdc++.h>
using namespace std;
int dist[200002];
int l[200002], r[200002];
vector<pair<int, int>> v;
int N; bool st1 = true;
int up[200002][21], dis[200002][21];
vector<int> H;
void init(int N_tmp, vector<int> H_tmp) {
N = N_tmp; H = H_tmp;
for(int i = 0; i < N; i++){
v.push_back({H[i], i + 1});
if(H[i] != i + 1) st1 = false;
}
sort(v.begin(), v.end(), greater<pair<int, int>>());
set<pair<int, int>> v2;
for(auto [x, tmp] : v){
if(v2.empty()){
v2.insert({tmp, x});
continue;
}
auto it = v2.lower_bound({tmp, 0});
// printf(">> %d %d : %d %d\n", x, tmp, (*it).first, (*it).second);
if(it != v2.end()) r[x] = (*it).second;
if(it != v2.begin()){
it--;
l[x] = (*it).second;
}
if((r[x] == 0 && l[x] != 0) || (l[x] < r[x] && l[x] != 0)) up[x][0] = l[x];
else if(l[x] == 0 || r[x] < l[x]) up[x][0] = r[x];
dis[x][0] = 1;
int i = 1;
if(l[x] != 0 && r[x] != 0){
up[x][1] = max(l[x], r[x]);
dis[x][1] = 1; i++;
}
// printf("!!! %d : %d %d: %d %d\n", x, l[x], r[x], up[x][0], up[x][1]);
for(; i <= 20; i++){
up[x][i] = up[up[x][i - 1]][i - 1];
dis[x][i] = dis[up[x][i - 1]][i - 1] + dis[x][i - 1];
}
v2.insert({tmp, x});
}
// for(int i = 1; i <= N; i++){
// for(int j = 0; j <= 3; j++){
// printf("up %d %d: %d\n", i, j, up[j][i]);
// }
// }
}
int minimum_jumps(int A, int B, int C, int D) {
if(st1) return C - B;
if(A == B && C == D){
B = H[B], C = H[C];
int ans = 0;
for(int i = 20; i >= 0; i--){
if(up[B][i] != 0 && up[B][i] < C){
// printf("%d ==> %d, %d\n", B, up[B][i], C);
ans += dis[B][i];
B = up[B][i];
}
}
// printf(">> %d %d\n", up[B][0], B);
if(up[B][0] != C) return -1;
return ans + dis[B][0];
}
int ans = 1000000000; A++; B++; C++; D++;
for(int i = 0; i <= N; i++) dist[i] = 1000000000;
for(auto [x, idx]: v){
if(idx >= C && idx <= D) dist[x] = 0;
if(idx >= A && idx <= B) ans = min({ans, dist[l[x]] + 1, dist[r[x]] + 1});
dist[x] = min({dist[x], dist[l[x]] + 1, dist[r[x]] + 1});
// printf(">> %d (%d, %d) : %d %d\n", x, l[x], r[x], dist[l[x]], dist[r[x]]);
}
return ans == 1000000000 ? -1 : ans;
}
