#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define f first
#define s second
int n,h[200005];
int bk[200005][20],ft[200005][20];
vector<int> jp[200005];
void monotone_q_and_lds()
{
for(int i = 0; i < n; i++)
bk[i][0] = i;
memset(ft,-1,sizeof(ft));
stack<int> s;
for(int i = 0; i < n; i++)
{
if(s.size())
while(!s.empty() && h[s.top()] < h[i])
{
// s top go right that is i
jp[s.top()].pb(i);
ft[s.top()][0] = i;
s.pop();
}
if(!s.empty())
{
// i go left that is s top
jp[i].pb(s.top());
bk[i][0] = s.top();
}
s.push(i);
}
}
int spa[2][200005][20],far_go[200005][20];
void gen_spa()
{
memset(spa,-1,sizeof(spa));
for(int i = 0; i < n; i++)
{
if(sz(jp[i]) > 0)
spa[0][i][0] = jp[i][0];
if(sz(jp[i]) > 1)
spa[1][i][0] = jp[i][1];
far_go[i][0] = spa[1][i][0];
}
for(int j = 1; j < 20; j++)
{
for(int i = 0; i < n; i++)
{
if(spa[0][i][j - 1] != -1)
{
spa[0][i][j] = spa[0][spa[0][i][j - 1]][j - 1];
}
if(spa[1][i][j - 1] != -1)
{
spa[1][i][j] = spa[1][spa[1][i][j - 1]][j - 1];
far_go[i][j] = max(far_go[i][j - 1], far_go[spa[1][i][j - 1]][j - 1]);
}
bk[i][j] = bk[bk[i][j - 1]][j - 1];
if(ft[i][j - 1] != -1)
ft[i][j] = ft[ft[i][j - 1]][j - 1];
}
}
}
int rmq[200005][20];
int pre_len[200005];
void gen_rmq()
{
memset(rmq,0,sizeof(rmq));
for(int i = 0; i < n; i++)
rmq[i][0] = h[i];
for(int j = 1; j < 20; j++)
{
for(int i = 0; i < n; i++)
{
if(i + (1 << j) - 1 >= n) continue;
int mid = i + (1 << (j - 1));
rmq[i][j] = max(rmq[i][j - 1], rmq[mid][j - 1]);
}
}
pre_len[1] = 0;
for(int i = 2; i < 200005; i++)
{
pre_len[i] = pre_len[i - 1];
if(i == (1 << (pre_len[i] + 1))) pre_len[i]++;
}
}
void init(int N, vector<int> H)
{
// input
n = N;
for(int i = 0; i < n; i++)
h[i] = H[i];
// jump
monotone_q_and_lds();
for(int i = 0; i < n; i++)
sort(all(jp[i]), [&](const int &x, const int &y) {
return h[x] < h[y];
});
// jump sparse table
gen_spa();
// rmq
gen_rmq();
}
int qu_rmq(int l,int r)
{
int qu_sz = pre_len[r - l + 1];
int mid = r - (1 << qu_sz) + 1;
return max(rmq[l][qu_sz], rmq[mid][qu_sz]);
}
int qu_mx_s(int l,int r,int mx)
{
int ret = r;
for(int j = 19; j >=0; j--)
{
if(l <= bk[ret][j] && h[bk[ret][j]] < mx)
ret = bk[ret][j];
}
return ret;
}
int qu_mn_step(int s,int l,int r,int mx)
{
int nw = s;
int ret = 0;
for(int j = 19; j >= 0; j--)
{
if(spa[1][nw][j] == -1) continue;
if(far_go[nw][j] < l && spa[0][nw][j] < l && spa[1][nw][j] < l && h[spa[1][nw][j]] < mx)
nw = spa[1][nw][j], ret += (1 << j);
}
for(int j = 19; j >= 0; j--)
{
if(ft[nw][j] == -1) continue;
if(ft[nw][j] < l && h[ft[nw][j]] < mx)
nw = ft[nw][j], ret += (1 << j);
}
if(ft[nw][0] < l || ft[nw][0] > r )
return -1;
return ret + 1;
}
int minimum_jumps(int A, int B, int C, int D)
{
int mx = qu_rmq(C, D);
int s = qu_mx_s(A, B, mx);
if(h[s] > mx) return -1;
return qu_mn_step(s, C, D, mx);
}
