#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int mxn = 2e5+23, lg = 23;
int l[mxn][lg], r[mxn][lg], jmp[mxn][lg];
int n;
vector<int> h;
void init(int nn, vector<int> hh)
{
n = nn;
h = hh;
h.insert(h.begin(), 1e9);
h.push_back(1e9);
stack<pair<int, int>> s;
n = h.size();
for(int i = 0; i < n; i++)
{
while(s.size() && (s.top().first < h[i]))
{
s.pop();
}
if(s.size())
{
l[i][0] = s.top().second;
}
else
{
l[i][0] = i;
}
s.push({h[i], i});
}
while(s.size())
{
s.pop();
}
for(int i = n-1; i >= 0; i--)
{
while(s.size() && (s.top().first < h[i]))
{
s.pop();
}
if(s.size())
{
r[i][0] = s.top().second;
}
else
{
r[i][0] = i;
}
s.push({h[i], i});
}
for(int i = 0; i <= n; i++)
{
jmp[i][0] = r[i][0];
if(h[l[i][0]] > h[r[i][0]])
{
jmp[i][0] = l[i][0];
}
}
for(int i = 1; i < lg; i++)
{
for(int v = 0; v <= n; v++)
{
l[v][i] = l[l[v][i-1]][i-1];
r[v][i] = r[r[v][i-1]][i-1];
jmp[v][i] = jmp[jmp[v][i-1]][i-1];
}
}
}
int minimum_jumps(int a, int b, int c, int d)
{
a++;
b++;
c++;
d++;
if((c-b) == 1)
{
if(r[b][0] > d)
{
return -1;
}
else
{
return 1;
}
}
int m = b+1;
for(int i = lg-1; i >= 0; i--)
{
if(r[m][i] < c)
{
m = r[m][i];
}
}
if(h[b] > h[m])
{
if(r[b][0] > d)
{
return -1;
}
else
{
return 1;
}
}
int v = b;
for(int i = lg-1; i >= 0; i--) // best start
{
if((a <= l[v][i]) && (h[l[v][i]] < h[m]))
{
v = l[v][i];
}
}
int cnt = 0;
if(a <= l[v][0])
{
if(r[l[v][0]][0] <= d)
{
return 1;
}
}
else
{
for(int i = lg-1; i >= 0; i--)
{
if(h[jmp[v][i]] <= h[m])
{
cnt += (1 << i);
v = jmp[v][i];
}
}
if(v == m)
{
if(r[v][0] > d)
{
return -1;
}
else
{
return ++cnt;
}
}
if((0 < l[v][0]) && (r[l[v][0]][0] <= d))
{
return cnt+2;
}
}
for(int i = lg-1; i >= 0; i--)
{
if(r[v][i] < c)
{
cnt += (1<<i);
v = r[v][i];
}
}
if((r[v][0] < c) || (r[v][0] > d))
{
return -1;
}
else
{
return ++cnt;
}
}
