#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
//#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
//const int INF=1000000000000000000;
const int INF=1e9;
const int N=1000000;
const int M=7+1e9;
const int ln=20;
struct Mint{
int n;
Mint(int nn){
n=nn%M;
}
Mint(){
n=0;
}
Mint& operator+=(Mint const& m){
n=(n+m.n)%M;
return *this;
}
Mint& operator*=(Mint const& m){
n=(n*m.n)%M;
return *this;
}
Mint& operator-=(Mint const& m){
n=(n+M-m.n)%M;
return *this;
}
friend Mint binpow(Mint a,int b){
if(b==0) return Mint(1);
Mint r=binpow(a,b/2LL);
r*=r;
if(b%2==0) return r;
r*=a;
return r;
}
friend Mint inverse(Mint a){
return binpow(a,M-2);
}
Mint& operator/=(Mint const &b){
return (*this)*=inverse(b);
}
friend Mint operator+(Mint a,Mint const b){
return (a+=b);
}
friend Mint operator-(Mint a,Mint const b){
return (a-=b);
}
friend Mint operator*(Mint a,Mint const b){
return (a*=b);
}
friend Mint operator/(Mint a,Mint const b){
return (a/=b);
}
friend Mint operator-(Mint a){
return 0-a;
}
friend std::ostream& operator<<(std::ostream& os, Mint const& a){
return os << a.n;
}
friend std::istream& operator>>(std::istream& is, Mint& a){
return (is >> a.n);
}
friend bool operator==(Mint const& a,Mint const& b){
return a.n==b.n;
}
friend bool operator!=(Mint const& a,Mint const& b){
return a.n!=b.n;
}
};
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
return os << p.fi << " " << p.se << "\n";
}
int n;
vector<int> h;
vector<int> big[ln];
vector<int> sm[ln];
vector<int> fr;
vector<int> fl;
int seg[2*N];
vector<int> invh;
void build(){
for(int i=n;i<2*n;i++){
seg[i]=h[i-n];
}
for(int i=n-1;i>=1;i--){
seg[i]=max(seg[2*i],seg[2*i+1]);
}
}
int query(int l,int r){
l+=n;
r+=n;
int ans=-1;
while(l<r){
if(l&1) ans=max(ans,seg[l++]);
if(r&1) ans=max(ans,seg[--r]);
l>>=1;
r>>=1;
}
return ans;
}
int queryrm(int l,int r,int val){
if(r==l+1){
if(h[l]>=val) return l;
return -1;
}
int m=(l+r)/2;
if(query(m,r)>=val){
return queryrm(m,r,val);
} else return queryrm(l,m,val);
}
void getfr(){
stack<int> s;
s.push(n);
for(int i=n-1;i>=0;i--){
while(s.top()!=n && h[s.top()]<h[i]){
s.pop();
}
fr[i]=s.top();
s.push(i);
}
}
void getfl(){
stack<int> s;
s.push(n);
for(int i=0;i<n;i++){
while(s.top()!=n && h[s.top()]<h[i]){
s.pop();
}
fl[i]=s.top();
s.push(i);
}
}
void init(int nn,vector<int> hh){
n=nn;
h=hh;
for(int i=0;i<n+1;i++) invh.push_back(0);
for(int i=0;i<n;i++) invh[h[i]]=i;
h.push_back(INF);
for(int i=0;i<n;i++){
fr.push_back(n);
fl.push_back(-1);
}
getfr();
getfl();
for(int i=0;i<ln;i++){
for(int j=0;j<n+1;j++){
big[i].push_back(n);
sm[i].push_back(n);
}
}
for(int i=0;i<n;i++){
if(h[fl[i]]>h[fr[i]]){
big[0][i]=fl[i];
sm[0][i]=fr[i];
} else{
big[0][i]=fr[i];
sm[0][i]=fl[i];
}
}
big[0][n]=n;
sm[0][n]=n;
for(int j=1;j<ln;j++){
for(int i=0;i<n;i++){
sm[j][i]=sm[j-1][sm[j-1][i]];
big[j][i]=big[j-1][big[j-1][i]];
}
}
build();
}
int minimum_jumps(int a,int b,int c,int d){
int mx=query(c,d+1);
int t=query(b+1,c);
int rmind=queryrm(a,b+1,t);
if(rmind!=-1){
if(fr[rmind]<=d) return 1;
}
if(rmind==b){
return -1;
}
int ind;
if(rmind==-1){
ind=invh[query(a,b+1)];
} else ind=invh[query(rmind+1,b+1)];
int fans=0;
for(int j=ln-1;j>=0;j--){
if(h[big[j][ind]]<t){
ind=big[j][ind];
fans+=(1<<j);
}
}
if(h[big[0][ind]]<mx) return fans+2;
for(int j=ln-1;j>=0;j--){
if(h[sm[j][ind]]<=mx && sm[j][ind]<c){
ind=sm[j][ind];
fans+=(1<<j);
}
}
if(sm[0][ind]<=d && sm[0][ind]>=c) return fans+1;
return -1;
}
