#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10, maxlog = 21;
int n, h[maxn], left_child[maxn], right_child[maxn];
int dp[maxlog][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] = 0;
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);
}
h[0] = 1e9;
for (int i = 1; i <= n; i ++)
{
if (h[left_child[i]] > h[right_child[i]])
dp[0][i] = left_child[i];
else
dp[0][i] = right_child[i];
}
for (int j = 1; j < maxlog; j ++)
for (int i = 1; i <= n; i ++)
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
int used[maxn];
int minimum_jumps(int A, int B, int C, int D)
{
A ++;
B ++;
C ++;
D ++;
if (A == B && C == D)
{
int ver = A, ans = 0;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (h[dp[bit][ver]] < h[C])
{
ans = ans + (1 << bit);
ver = dp[bit][ver];
}
}
if (left_child[ver] != C && right_child[ver] != C)
return -1;
return ans + 1;
}
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] != 0 && used[left_child[cur]] == 0)
{
used[left_child[cur]] = used[cur] + 1;
q.push(left_child[cur]);
}
if (right_child[cur] != 0 && 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;
}
