#include "jumps.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 20;
const llong INF = 1e18;
const int INTINF = 2e9;
int n;
int h[MAXN];
int firstR[MAXN];
int firstL[MAXN];
std::stack <int> st;
void init(int N, std::vector <int> H)
{
n = N;
for (int i = 0 ; i < n ; ++i)
{
h[i + 1] = H[i];
}
h[0] = h[n + 1] = INTINF;
st.push(0);
for (int i = 1 ; i <= n ; ++i)
{
while (st.size() && h[i] > h[st.top()])
{
st.pop();
}
firstL[i] = st.top();
st.push(i);
}
while (st.size()) st.pop();
st.push(n + 1);
for (int i = n ; i >= 1 ; --i)
{
while (st.size() && h[i] > h[st.top()])
{
st.pop();
}
firstR[i] = st.top();
st.push(i);
}
}
int minimum_jumps(int a, int b, int c, int d)
{
a++; b++; c++; d++;
int pos = -1;
int maxC = 0;
for (int i = c ; i <= d ; ++i)
{
maxC = std::max(maxC, h[i]);
}
for (int i = a ; i <= b ; ++i)
{
if (h[i] <= maxC && firstR[i] > b)
{
pos = i;
break;
}
}
if (pos == -1)
{
return -1;
}
int res = 0;
while (pos < c)
{
if (h[firstL[pos]] > maxC && h[firstR[pos]] > maxC)
{
return -1;
}
if (h[firstL[pos]] <= maxC && (firstR[pos] > d || h[firstL[pos]] > h[firstR[pos]]))
{
res++;
pos = firstL[pos];
} else
{
res++;
pos = firstR[pos];
}
}
return res;
}
