#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int N=200010, L=20;
int n, a[N], nxt1[L][N], nxt2[L][N];
pair<int, int> mxl[L][N], mxr[L][N], mnl[L][N], mnr[L][N];
vector<int> stk;
void init(int N, vector<int> H) {
n=N;
for(int i=1; i<=n; i++) a[i]=H[i-1];
for(int i=1; i<=n; i++) mxl[0][i]=mxr[0][i]=mnl[0][i]=mnr[0][i]={a[i], i};
for(int i=1; i<L; i++) {
for(int j=1; j<=n; j++) {
if(j+(1<<i)-1<=n) {
mxl[i][j]=max(mxl[i-1][j], mxl[i-1][j+(1<<(i-1))]);
mnl[i][j]=min(mnl[i-1][j], mnl[i-1][j+(1<<(i-1))]);
}
if(j-(1<<i)+1>=1) {
mxr[i][j]=max(mxr[i-1][j], mxr[i-1][j-(1<<(i-1))]);
mnr[i][j]=min(mnr[i-1][j], mnr[i-1][j-(1<<(i-1))]);
}
}
}
for(int i=n; i>=1; i--) {
while(!stk.empty() && a[stk.back()]<=a[i]) stk.pop_back();
if(!stk.empty()) nxt1[0][i]=nxt2[0][i]=stk.back();
stk.push_back(i);
}
stk.clear();
for(int i=1; i<=n; i++) {
while(!stk.empty() && a[stk.back()]<=a[i]) stk.pop_back();
if(!stk.empty() && a[nxt1[0][i]]<a[stk.back()]) nxt1[0][i]=stk.back();
stk.push_back(i);
}
for(int i=1; i<L; i++) for(int j=1; j<=n; j++) {
nxt1[i][j]=nxt1[i-1][nxt1[i-1][j]], nxt2[i][j]=nxt2[i-1][nxt2[i-1][j]];
}
}
pair<int, int> querymn(int l, int r) {
int tmp=31-__builtin_clz(r-l+1);
return min(mnl[tmp][l], mnr[tmp][r]);
}
pair<int, int> querymx(int l, int r) {
if(l>r) return {0, 0};
int tmp=31-__builtin_clz(r-l+1);
return max(mxl[tmp][l], mxr[tmp][r]);
}
int queryp(int l, int r, int x) {
int p=r;
for(int i=L-1; i>=0; i--) if(mxr[i][p-1].first && mxr[i][p-1].first<x) p-=(1<<i);
return max(l, p);
}
int queryq(int l, int r, int x) {
for(int i=L-1; i>=0; i--) if(mxl[i][l].first && mxl[i][l].first<=x) l+=(1<<i);
return min(r, l);
}
int query(int l, int lo, int hi) {
if(a[l]>=lo && a[l]<hi) return 0;
int ret=0;
for(int i=L-1; i>=0; i--) if(nxt1[i][l] && a[nxt1[i][l]]<lo) ret+=(1<<i), l=nxt1[i][l];
if(a[nxt1[0][l]]<hi) return ret+1;
for(int i=L-1; i>=0; i--) if(nxt2[i][l] && a[nxt2[i][l]]<lo) ret+=(1<<i), l=nxt2[i][l];
return ret+1;
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
pair<int, int> x=querymx(B+1, C-1), mx2=querymx(C, D);
if(a[B]>=mx2.first || (B+1<C && x.first>=mx2.first)) return -1;
A=queryp(A, B, mx2.first);
pair<int, int> mx1=querymx(A, B);
if(x.second) return query(mx1.second, x.first, mx2.first)+1;
return query(mx1.second, 0, mx2.first)+1;
}
