#include "jumps.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
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::vector <int> g[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 (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 (h[i] > h[st.top()])
{
st.pop();
}
firstR[i] = st.top();
st.push(i);
}
for (int i = 1 ; i <= n ; ++i)
{
g[i].push_back(firstL[i]);
g[i].push_back(firstR[i]);
}
}
int dists[MAXN];
std::queue <int> q;
int minimum_jumps(int a, int b, int c, int d)
{
return c - b;
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;
}
std::fill(dists + 1, dists + 1 + n, -1);
dists[pos] = 0;
q.push(pos);
while (!q.empty())
{
int top = q.front();
q.pop();
for (const int &u : g[top])
{
if (dists[u] == -1)
{
dists[u] = dists[top] + 1;
q.push(u);
}
}
}
int min = a;
for (int i = a + 1 ; i <= b ; ++i)
{
if (dists[i] != -1 && (dists[min] == -1 || dists[min] > dists[i]))
{
min = i;
}
}
return dists[min];
}
