#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
int l[20][200001], r[20][200001], nxt[20][200001], res;
vector<int> v;
void init(int N, vector<int> H)
{
for (int i = 0; i < 20; ++i)
{
fill_n(l[i], N + 1, N);
fill_n(r[i], N + 1, N);
fill_n(nxt[i], N + 1, N);
}
H.push_back(0);
v.clear();
for (int i = 0; i < N; ++i)
{
while (!v.empty() && H[v.back()] <= H[i])
v.pop_back();
l[0][i] = (v.empty() ? N : v.back());
v.push_back(i);
}
v.clear();
for (int i = N - 1; i > -1; --i)
{
while (!v.empty() && H[v.back()] <= H[i])
v.pop_back();
r[0][i] = (v.empty() ? N : v.back());
v.push_back(i);
}
for (int i = 0; i < N; ++i)
nxt[0][i] = (H[l[0][i]] > H[r[0][i]] ? l[0][i] : r[0][i]);
for (int i = 1; i < 20; ++i)
for (int j = 0; j < N; ++j)
{
l[i][j] = l[i - 1][l[i - 1][j]];
r[i][j] = r[i - 1][r[i - 1][j]];
nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
}
}
int minimum_jumps(int A, int B, int C, int D)
{
res = 0;
for (int i = 19; i > -1; --i)
if (A <= l[i][B] && r[0][l[i][B]] <= D)
B = l[i][B];
if (C <= r[0][B] && r[0][B] <= D)
return 1;
for (int i = 19; i > -1; --i)
if (r[0][nxt[i][B]] < C)
{
B = nxt[i][B];
res += (1 << i);
}
if (r[0][nxt[0][B]] <= D)
return res + 2;
for (int i = 19; i > -1; --i)
if (r[i][B] < C)
{
B = r[i][B];
res += (1 << i);
}
return (C <= r[0][B] && r[0][B] <= D ? res + 1 : -1);
}
