#include "jumps.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <iostream>
using namespace std;
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
const ld PI = 3.1415926535;
const int N = 5e5+10;
const int M = 1e4 + 5;
int mod = 1e9+7;
const int P = 467743;
const int K = 20;
int h[N], n, lu[N], ru[N], up1[N][K], up2[N][K], whr[N];
struct sparset{
int st[N][K];
int mx[N][K];
void init(){
for(int i = 1; i <= n; i++)
st[i][0] = h[i], mx[i][0] = h[i];
for(int k = 1; k < K; k++)
for(int i = 1; i + (1 << k) - 1 <= n; i++)
st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
for(int k = 1; k < K; k++)
for(int i = 1; i + (1 << k) - 1 <= n; i++)
mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
}
int getmn(int l, int r){
int g = __lg(r - l + 1);
return min(st[l][g], st[r - (1 << g) + 1][g]);
}
int getmx(int l, int r){
int g = __lg(r - l + 1);
return max(mx[l][g], mx[r - (1 << g) + 1][g]);
}
} st;
void init(int _n, std::vector<int> H) {
n = _n;
for(int i = 0; i < n; i++)
h[i + 1] = H[i], whr[H[i]] = i + 1;
vector<pii> ps = {};
st.init();
for(int i = 1; i <= n; i++){
ps.pb({h[i], i});
int lo = 0, hi = i;
while(lo + 1 < hi){
int m = (lo + hi) / 2;
if(st.getmx(m, i) > h[i])
lo = m;
else
hi = m;
}
lu[i] = lo;
lo = i, hi = n + 1;
while(lo + 1 < hi){
int m = (lo + hi) / 2;
if(st.getmx(i, m) > h[i])
hi = m;
else
lo = m;
}
ru[i] = hi;
}
sort(all(ps));
for(int k = 0; k < K; k++)
up1[n + 1][k] = up2[n + 1][k] = n + 1;
ru[n + 1] = n + 1;
for(int i = sz(ps) - 1; i >= 0; i--){
int pos = ps[i].S;
if(lu[pos] == 0 && ru[pos] == n + 1){
for(int k = 0; k < K; k++)
up1[pos][k] = n + 1;
}else if(lu[pos] == 0){
up1[pos][0] = ru[pos];
for(int k = 1; k < K; k++)
up1[pos][k] = up1[up1[pos][k - 1]][k - 1];
}else if(ru[pos] == n + 1){
up1[pos][0] = lu[pos];
for(int k = 1; k < K; k++)
up1[pos][k] = up1[up1[pos][k - 1]][k - 1];
}else{
if(h[lu[pos]] > h[ru[pos]])
up1[pos][0] = lu[pos];
else
up1[pos][0] = ru[pos];
for(int k = 1; k < K; k++)
up1[pos][k] = up1[up1[pos][k - 1]][k - 1];
}
}
for(int i = n; i >= 1; i--){
up2[i][0] = ru[i];
for(int k = 1; k < K; k++){
up2[i][k] = up2[up2[i][k - 1]][k - 1];
}
}
}
int getans(int st, int C, int D){
int ret = 0;
for(int k = K - 1; k >= 0; k--){
if(ru[up1[st][k]] < C)
st = up1[st][k], ret += (1 << k);
}
if(ru[up1[st][0]] <= D && ru[up1[st][0]] >= C){
return ret + 2;
}
for(int k = K - 1; k >= 0; k--){
if(up2[st][k] < C)
st = up2[st][k], ret += (1 << k);
}
if(ru[st] <= D && ru[st] >= C){
return ret + 1;
}
return -1;
}
int minimum_jumps(int A, int B, int C, int D) {
A++;
B++;
C++;
D++;
int ret = -1;
for(int i = A; i <= B; i++){
int r = getans(i, C, D);
if(r == -1)
continue;
if(ret == -1){
ret = r;
}else{
ret = min(ret, r);
}
}
return ret;
}
/*signed main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int A, B, C, D;
assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}*/
