#include "jumps.h"
#include <vector>
using namespace std;
const int logn = 19, maxn = 2e5+5;
//const int logn = 19, maxn = 10;
int jumpl[logn][maxn], jumpr[logn][maxn], high[logn][maxn];
int n, top, h[maxn], stk[maxn];
void init(int N, vector<int> H)
{
n = N, top = 0;
for (int i = 1; i <= n; i++) h[i] = H[i - 1];
for (int i = 1; i <= n; i++)
{
while (top && h[stk[top - 1]] < h[i]) jumpr[0][stk[top - 1]] = i, top--;
if (top) jumpl[0][i] = stk[top - 1];
stk[top++] = i;
}
for (int i = 1; i <= n; i++)
{
int l = jumpl[0][i], r = jumpr[0][i];
if (!r || (l && r && h[l] > h[r])) high[0][i] = l;
else high[0][i] = r;
}
for (int l = 1; l < logn; l++) for (int i = 1; i <= n; i++)
{
jumpl[l][i] = jumpl[l - 1][jumpl[l - 1][i]];
jumpr[l][i] = jumpr[l - 1][jumpr[l - 1][i]];
high[l][i] = high[l - 1][high[l - 1][i]];
}
}
int minimum_jumps(int a, int b, int c, int d)
{
a++, b++, c++, d++;
for (int l = logn - 1; l >= 0; l--)
if (jumpl[l][d] >= c)
d = jumpl[l][d];
for (int l = logn - 1; l >= 0; l--)
if (jumpl[l][b] >= a && h[jumpl[l][b]] <= h[d])
b = jumpl[l][b];
int mx = b; // kym sme nizsie ako mx = maximum ktore budeme musiet prejst, mozeme si chodit ako chceme.
for (int l = logn - 1; l >= 0; l--)
if (jumpr[l][mx] && jumpr[l][mx] < c)
mx = jumpr[l][mx];
int i = b, ans = 0;
for (int l = logn - 1; l >= 0; l--)
if (high[l][i] && h[high[l][i]] <= h[mx])
i = high[l][i], ans += (1 << l);
// i zatial nemoze byt v intervale kde je odpoved, lebo potrebujeme prejst maximum.
if (jumpr[0][i] >= c && jumpr[0][i] <= d) return ans + 1;
if (high[0][i] && h[high[0][i]] <= h[d])
i = high[0][i], ans++;
for (int l = logn - 1; l >= 0; l--)
if (jumpr[l][i] && jumpr[l][i] < c)
i = jumpr[l][i], ans += (1 << l);
i = jumpr[0][i], ans++;
if (c <= i && i <= d) return ans;
return -1;
}
