#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
// void setup()
// {
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// #endif
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// }
int l[20][200001], r[20][200001], nxt[20][200001], res;
vector<int> v;
void init(int N, vector<int> H)
{
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 >= 0; --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 >= 0; --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 >= 0; --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 >= 0; --i)
{
if (r[i][B] < C)
{
B = r[i][B];
res += (1 << i);
}
}
return (r[0][B] <= D ? res + 1 : -1);
}
// int main()
// {
// setup();
// return 0;
// }
