#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
int n, q, lpos, rpos, des, mid, sta, res;
int h[200000], l[200000], r[200000];
int high[20][200000], low[20][200000], sp[20][200000];
vector<int> v;
inline int Get_sp(int _l, int _r)
{
int _k = __lg(_r - _l + 1);
_l = sp[_k][_l];
_r = sp[_k][_r - (1 << _k) + 1];
return (h[_l] > h[_r] ? _l : _r);
}
inline int Go(int start_pos, int end_pos)
{
int ret = 0;
for (int i = 19, j; i >= 0; --i)
{
j = high[i][start_pos];
if (j != -1 && h[j] < h[end_pos])
{
start_pos = j;
ret += (1 << i);
}
}
for (int i = 19, j; i >= 0; --i)
{
j = low[i][start_pos];
if (j != -1 && h[j] < h[end_pos])
{
start_pos = j;
ret += (1 << i);
}
}
return ret + 1;
}
void init(int N, int(H[]))
{
n = N;
for (int i = 0; i < n; ++i)
{
h[i] = H[i];
}
for (int i = 0; i < n; ++i)
{
cin >> h[i];
while (!v.empty() && h[v.back()] <= h[i])
{
v.pop_back();
}
l[i] = (v.empty() ? -1 : 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[i] = (v.empty() ? -1 : v.back());
v.push_back(i);
high[0][i] = (l[i] == -1 ? r[i] : (r[i] == -1 ? l[i] : (h[l[i]] > h[r[i]] ? l[i] : r[i])));
low[0][i] = (l[i] == -1 ? r[i] : (r[i] == -1 ? l[i] : (h[l[i]] < h[r[i]] ? l[i] : r[i])));
sp[0][i] = i;
}
for (int i = 1; i < 20; ++i)
{
for (int j = 0; j < n; ++j)
{
lpos = high[i - 1][j];
high[i][j] = (lpos == -1 ? -1 : high[i - 1][lpos]);
lpos = low[i - 1][j];
low[i][j] = (lpos == -1 ? -1 : low[i - 1][lpos]);
}
for (int j = 0; j + (1 << i) <= n; ++j)
{
lpos = sp[i - 1][j];
rpos = sp[i - 1][j + (1 << (i - 1))];
sp[i][j] = (h[lpos] > h[rpos] ? lpos : rpos);
}
}
}
int minimum_jumps(int a, int b, int c, int d)
{
des = Get_sp(c, d);
mid = (b + 1 < c ? Get_sp(b + 1, c - 1) : -1);
sta = -1;
for (int i = 19, j = b + 1; i >= 0; --i)
{
if (a <= j - (1 << i) && h[Get_sp(j - (1 << i), b)] < h[des])
{
j -= (1 << i);
sta = Get_sp(j, b);
}
}
if (sta == -1 || (mid != -1 && h[mid] >= h[des]))
{
return -1;
}
if (mid == -1)
{
return (h[b] <= h[des] ? 1 : -1);
}
if (h[sta] >= h[mid])
{
res = Go(sta, des);
}
else
{
res = Go(sta, mid) + 1;
if (l[mid] != -1 && h[l[mid]] < h[des])
{
res = min(res, Go(sta, l[mid]) + 1);
}
}
return res;
}
// int main()
// {
// return 0;
// }
