#include "jumps.h"
#include<bits/stdc++.h>
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
using namespace std;
const int N = 200000+10, K = 20;
int n, dp[N][K], R[N], A[N], up[N][K];
vector<int> T[4*N];
void build(int l, int r, int k){
if(l == r){
T[k] = {R[l]};
return;
}
int m = l+r>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
merge(all(T[k<<1]), all(T[k<<1|1]), back_inserter(T[k]));
}
int get_max(int l, int r, int ql, int qr, int k, int X, int Y){
if(ql > r || l > qr) return -1;
if(ql <= l && r <= qr){
int pos = upper_bound(all(T[k]), Y) - T[k].begin();
if(pos > 0){
int val = T[k][pos - 1];
return (val >= X ? val : -1);
}
return -1;
}
int m = l+r>>1;
return max(get_max(l, m, ql, qr, k<<1, X, Y), get_max(m+1, r, ql, qr, k<<1|1, X, Y));
}
int get(int l, int r){
int k = int(log2(r-l+1));
if(A[dp[l][k]] >= A[dp[r - (1<<k) + 1][k]])
return dp[l][k];
return dp[r - (1<<k) + 1][k];
}
void init(int _N, std::vector<int> H) {
n = _N;
for(int i = 1; i <= n; ++i) A[i] = H[i - 1];
for(int i = 1; i <= n; ++i) dp[i][0] = i;
for(int j = 1; j < K; ++j)
for(int i = 1; i + (1<<j) <= n + 1; ++i){
if(A[dp[i][j - 1]] >= A[dp[i+(1<<(j-1))][j - 1]])
dp[i][j] = dp[i][j - 1];
else
dp[i][j] = dp[i+(1<<(j-1))][j - 1];
}
R[n] = n + 1;
deque<int> q;
q.pb(n);
for(int i = n - 1; i >= 1; --i){
while(!q.empty() && A[q.front()] <= A[i]) q.pop_front();
if(q.empty()) R[i] = n + 1;
else R[i] = q.front();
q.push_front(i);
}
build(1, n, 1);
R[n + 1] = n + 1;
for(int i = 1; i <= n + 1; ++i) up[i][0] = R[i];
for(int j = 1; j < K; ++j)
for(int i = 1; i <= n + 1; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
int ans = mod, M = 0;
if(B < C - 1){
M = get(B+1, C-1);
int v = M, co = 0;
for(int j = K - 1; j >= 0; --j){
if(up[v][j] <= D)
v = up[v][j], co += (1<<j);
if(v >= C) break;
}
if(v >= C){
int p = get_max(1, n, A, B, 1, B+1, M);
if(p != -1){
co++;
for(int j = K - 1; j >= 0; --j){
if(up[p][j] <= M)
p = up[p][j], co += (1<<j);
}
ans = co;
}
}
}
int co = 1;
int p = get_max(1, n, A, B, 1, M + 1, D);
if(p != -1){
for(int j = K - 1; j >= 0; --j){
if(p >= C) break;
if(up[p][j] <= D)
p = up[p][j], co += (1<<j);
}
ans = min(ans, co);
}
return (ans==mod?-1:ans);
}
