#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, h[maxn], left_child[maxn], right_child[maxn];
void init(int N, vector<int> H)
{
n = N;
for (int i = 0; i < N; i ++)
{
left_child[i + 1] = right_child[i + 1] = -1;
h[i + 1] = H[i];
}
stack < int > st;
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && h[i] > h[st.top()])
st.pop();
if (!st.empty())
left_child[i] = st.top();
st.push(i);
}
while(!st.empty())
st.pop();
for (int i = n; i > 0; i --)
{
while(!st.empty() && h[i] > h[st.top()])
st.pop();
if (!st.empty())
right_child[i] = st.top();
st.push(i);
}
}
int used[maxn];
void bfs(int v)
{
}
int minimum_jumps(int A, int B, int C, int D)
{
A ++;
B ++;
C ++;
D ++;
int ans = 1e9;
for (int i = 1; i <= n; i ++)
used[i] = 0;
queue < int > q;
for (int i = A; i <= B; i ++)
{
q.push(i);
used[i] = 1;
}
//cout << "------------" << endl;
while(!q.empty())
{
int cur = q.front();
q.pop();
///cout << cur << endl;
if (left_child[cur] != -1 && used[left_child[cur]] == 0)
{
used[left_child[cur]] = used[cur] + 1;
q.push(left_child[cur]);
}
if (right_child[cur] != -1 && used[right_child[cur]] == 0)
{
used[right_child[cur]] = used[cur] + 1;
q.push(right_child[cur]);
}
}
for (int to = C; to <= D; to ++)
{
///cout << "here "<< to << " " << used[to] << endl;
if (used[to] != 0)
{
ans = min(ans, used[to] - 1);
}
}
if (ans == 1e9)
return -1;
return ans;
}
