#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;
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;
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]];
}
}
}
int ans(int a,int b){
int fans=0;
for(int j=ln-1;j>=0;j--){
if(h[big[j][a]]<=h[b]){
a=big[j][a];
fans+=(1<<j);
}
}
for(int j=ln-1;j>=0;j--){
if(h[sm[j][a]]<=h[b]){
a=sm[j][a];
fans+=(1<<j);
}
}
if(a==b) return fans;
return INF;
}
int minimum_jumps(int a,int b,int c,int d){
int mx=INF;
for(int i=a;i<=b;i++) for(int j=c;j<=d;j++) mx=min(mx,ans(i,j));
if(mx!=INF) return mx;
return -1;
}
