#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int parent[200100][31];
int l[200100][31];
int r[200100][31];
int N;
vector<int> v;
vector<int> proc;
int st[200100 * 4];
void build(int i, int s, int e){
if(s != e){
int m = (s + e)/2;
build(i * 2, s,m);
build(i * 2 + 1, m + 1, e);
st[i] = max(st[i * 2],st[i * 2 + 1]);
}
else{
st[i] = v[s];
}
}
int query(int i, int s ,int e, int S, int E){
if(E < S) return 0;
if(S <= s && e <= E){
return st[i];
}
int m = (s + e)/2;
if(E <= m){
return query(i * 2, s,m, S,E);
}
if(m < S){
return query(i * 2 + 1, m + 1, e,S,E);
}
return max(query(i * 2, s,m, S,E),query(i * 2 + 1, m + 1, e,S,E));
}
void init(int n, std::vector<int> H) {
N = n;
v = H;
for(int i = 0; i < N; i++){
for(int j = 0; j < 30; j++){
l[i][j] = -1;
r[i][j] = -1;
parent[i][j] = -1;
}
}
for(int i = 0; i < N; i++){
while(!proc.empty() && v[proc.back()] < v[i]){
r[proc.back()][0] = i;
proc.pop_back();
}
proc.push_back(i);
}
proc.clear();
for(int i = N - 1; i > -1; i--){
while(!proc.empty() && v[proc.back()] < v[i]){
l[proc.back()][0] = i;
proc.pop_back();
}
proc.push_back(i);
}
proc.clear();
for(int i = 0; i < N; i++){
if(l[i][0] != -1){
parent[i][0] = l[i][0];
}
if(r[i][0] != -1 && (v[r[i][0]] > v[l[i][0]] || parent[i][0] == -1)){
parent[i][0] = r[i][0];
}
}
for(int j = 1; j < 30; j++){
for(int i = 0; i < N; i++){
if(l[i][j - 1] != -1){
l[i][j] = l[l[i][j - 1]][j - 1];
}
if(r[i][j - 1] != -1){
r[i][j] = r[r[i][j - 1]][j - 1];
}
if(parent[i][j - 1] != -1){
parent[i][j] = parent[parent[i][j - 1]][j - 1];
}
}
}
build(1,0,N-1);
}
int minimum_jumps(int A, int B, int C, int D) {
if(A <= C && C <= B){
return 0;
}
if(C <= A && A <= D){
return 0;
}
int steps = 0;
if(B < C){
if(query(1,0,N - 1, B + 1, C - 1) > query(1,0,N-1,C,D)){
return -1;
}
int m = query(1,0,N-1,C,D);
int h = B;
for(int i = 25; i > -1; i--){
if(l[h][i] == -1) continue;
if(l[h][i] >= A && v[l[h][i]] < m){
h = l[h][i];
}
}
if(v[h] > m){
return -1;
}
m = query(1,0,N - 1, B + 1, C - 1);
for(int i = 25; i > -1; i--){
if(parent[h][i] == -1) continue;
if(v[parent[h][i]] <= m){
h = parent[h][i];
steps += (1<<i);
}
}
for(int i = 25; i > -1; i--){
if(l[h][i] == -1) continue;
if(l[h][i] < C){
h = l[h][i];
steps += (1<<i);
}
}
}
if(C < B){
if(query(1,0,N - 1, D + 1, A - 1) > query(1,0,N-1,C,D)){
return -1;
}
int m = query(1,0,N-1,C,D);
int h = A;
for(int i = 25; i > -1; i--){
if(r[h][i] == -1) continue;
if(r[h][i] <= B && v[r[h][i]] < m){
h = r[h][i];
}
}
if(v[h] > m){
return -1;
}
m = query(1,0,N - 1, B + 1, C - 1);
for(int i = 25; i > -1; i--){
if(parent[h][i] == -1) continue;
if(v[parent[h][i]] <= m){
h = parent[h][i];
steps += (1<<i);
}
}
for(int i = 25; i > -1; i--){
if(r[h][i] == -1) continue;
if(r[h][i] < D){
h = r[h][i];
steps += (1<<i);
}
}
}
return steps + 1;
}
