#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], seg[2*maxn], hi[20][maxn], l[20][maxn], r[20][maxn], n, q;
inline int qry(int lx, int rx)
{
int ans = 0;
for (lx+=n, rx+=n+1; lx<rx; lx>>=1, rx>>=1)
{
if (lx & 1) ans = max(ans, seg[lx++]);
if (rx & 1) ans = max(ans, seg[--rx]);
}
return ans;
}
void init(int N, vector<int> H)
{
n = N;
for (int i=1; i<=n; i++) a[i] = H[i-1], seg[n+i] = a[i];
for (int i=n; i>=1; i--) seg[i] = max(seg[i<<1], seg[i<<1|1]);
vector<int> dq;
for (int i=n; i>=1; i--)
{
while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
r[0][i] = dq.size() ? dq.back() : -1;
dq.emplace_back(i);
}
dq.clear();
for (int i=1; i<=n; i++)
{
while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
l[0][i] = dq.size() ? dq.back() : -1;
dq.emplace_back(i);
}
// for (int i=1; i<=n; i++) hi[0][i] = (r[0][i] != -1 && (l[0][i] == -1 || a[r[0][i]] >= a[l[0][i]]) ? r[0][i] : l[0][i]);
// for (int i=1; i<=n; i++) cerr<<i<<" "<<l[0][i]<<" "<<r[0][i]<<"\n";
for (int i=1; i<=18; i++)
for (int j=1; j<=n; j++)
r[i][j] = (r[i-1][j] != -1 ? r[i-1][r[i-1][j]] : -1),
l[i][j] = (l[i-1][j] != -1 ? l[i-1][l[i-1][j]] : -1);//, cerr<<"SPT: "<<i<<" "<<j<<" "<<r[i][j]<<"\n";
// hi[i][j] = hi[i-1][hi[i-1][j]];
}
int minimum_jumps(int A, int B, int C, int D)
{
int ls, rs, le, re;
// cin>>ls>>rs>>le>>re;
ls = A, rs = B, le = C, re = D;
ls++, rs++, le++, re++;
if (qry(rs, le-1) >= qry(le, re)) return -1;
int cur = rs, mx = qry(le, re), ans = 0;
for (int i=18; i>=0; i--)
if (l[i][cur] != -1 && l[i][cur] >= ls && a[l[i][cur]] < mx) cur = l[i][cur];
for (int i=18; i>=0; i--)
if (r[i][cur] != -1 && r[i][cur] < le) ans += (1<<i), cur = r[i][cur];
return ans + 1;
}
//int main()
//{
//
//}
