#include<bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e9
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int LOGM = 19;
const int MX = 2e5+5;
vector<int> arr;
int l[LOGM][MX];
int r[LOGM][MX];
int up[LOGM][MX];
//min_jumps is now known to be correct. :)
int min_jumps(int x, int y)
{
int ans = 0;
for(int i = LOGM-1; i >= 0; i--)
{
int v = up[i][x];
if(arr[v] <= arr[y])
{
ans+=(1<<i);
x = v;
}
}
for(int i = LOGM-1; i >= 0; i--)
{
int v = r[i][x];
if(arr[v] <= arr[y])
{
ans+=(1<<i);
x = v;
}
}
if(x == y)
return ans;
return -1;
}
int minimum_jumps(int a, int b, int c, int d)
{
a++; b++; c++; d++;
int c1 = b;
for(int i = LOGM-1; i >= 0; i--)
{
int lift = r[i][c1];
if(lift < c)
c1 = lift;
}
c1 = r[0][c1];
if(c1 > d)
return -1;
int c2 = c1;
for(int i = LOGM-1; i >= 0; i--)
{
int lift = r[i][c2];
if(lift <= d)
c2 = lift;
}
int st = b;
for(int i = LOGM-1; i >= 0; i--)
{
int lift = l[i][st];
if((lift >= a) && (arr[lift] <= arr[c2]))
st = lift;
}
for(int i = LOGM-1; i >= 0; i--)
{
int lift = r[i][c1];
if(arr[lift] <= arr[st])
c1 = lift;
}
if(arr[c1] <= arr[st])
c1 = r[0][c1];
int one = min_jumps(st, c1);
int ans = 0;
for(int i = LOGM-1; i >= 0; i--)
{
int lift = up[i][st];
if(arr[lift] <= arr[c1])
{
ans+=(1<<i);
st = lift;
}
}
st = l[0][st];
if(arr[r[0][st]] <= arr[c2])
return min(one, ans+2);
else
return one;
}
void init(int n, vector<int> h)
{
arr.resize(n+2);
for(int i = 1; i <= n; i++)
arr[i] = h[i-1];
arr[0] = INF;
arr[n+1] = INF;
l[0][0] = 0;
r[0][0] = n+1;
l[0][n+1] = 0;
r[0][n+1] = n+1;
for(int i = 1; i <= n; i++)
{
l[0][i] = i-1;
r[0][i] = i+1;
}
for(int i = 1; i <= n; i++)
{
while(arr[l[0][i]] <= arr[i])
l[0][i] = l[0][l[0][i]];
}
for(int i = n; i >= 1; i--)
{
while(arr[r[0][i]] <= arr[i])
r[0][i] = r[0][r[0][i]];
}
for(int i = 0; i <= n+1; i++)
{
if(arr[l[0][i]] >= arr[r[0][i]])
up[0][i] = l[0][i];
else
up[0][i] = r[0][i];
}
for(int i = 1; i < LOGM; i++)
{
for(int u = 0; u <= n+1; u++)
{
l[i][u] = l[i-1][l[i-1][u]];
r[i][u] = r[i-1][r[i-1][u]];
up[i][u] = up[i-1][up[i-1][u]];
}
}
}
/*signed main()
{
init(7, {3, 2, 1, 6, 4, 5, 7});
int d = minimum_jumps(0, 1, 2, 2);
cout << d << endl;
}*/
