#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
using ll = long long;
using vll = vector<long long>;
constexpr ll inf = LONG_LONG_MAX;
constexpr ll max_n = 200005;
constexpr ll max_log = 20;
vector<vll> l;
vector<vll> r;
vector<vll> greedy;
void init(int n,vector<int> h)
{
h.push_back(-1);
vector<vll>(max_log,vll(max_n,n)).swap(l);
vector<vll>(max_log,vll(max_n,n)).swap(r);
vector<vll>(max_log,vll(max_n,n)).swap(greedy);
stack<int> s;
for(int i=0;i<n;i++)
{
while(!s.empty()&&h[s.top()]<h[i])
s.pop();
if(!s.empty())
l[0][i]=s.top();
s.push(i);
}
stack<int>().swap(s);
for(int i=n-1;i>=0;i--)
{
while(!s.empty()&&h[s.top()]<h[i])
s.pop();
if(!s.empty())
r[0][i]=s.top();
s.push(i);
}
for(int i=0;i<n;i++)
{
if(h[l[0][i]]>h[r[0][i]])
greedy[0][i]=l[0][i];
else
greedy[0][i]=r[0][i];
}
for(int i=1;i<max_log;i++)
{
for(int j=0;j<n;j++)
{
l[i][j]=l[i-1][l[i-1][j]];
r[i][j]=r[i-1][r[i-1][j]];
greedy[i][j]=greedy[i-1][greedy[i-1][j]];
}
}
}
int minimum_jumps(int a, int b, int c, int d)
{
int ans=0;
for(int i=max_log-1;i>=0;i--)
if(l[i][b]>=a&&r[0][l[i][b]]<=d)
b=l[i][b];
if(c<=r[0][b]&&r[0][b]<=d)
return 1;
for(int i=max_log-1;i>=0;i--)
{
if(r[0][greedy[i][b]]<c)
{
ans+=(1ll<<i);
b=greedy[i][b];
}
}
if(r[0][greedy[0][b]]<=d)
return ans+2;
for(int i=max_log-1;i>=0;i--)
{
if(r[i][b]<c)
{
ans+=(1ll<<i);
b=r[i][b];
}
}
if (r[0][b]<c||r[0][b]>d) return -1;
else return ans+1;
}
