#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h;
vector<vector<int> > twokr, twok, twokl;
void init(int n, vector<int> H){
h.resize(n+2, INT_MAX/2);
for (int i=0; i<n; ++i)h[i+1]=H[i];
vector<int> l(n+2), r(n+2);
stack<int> st;
st.push(0);
for (int i=1; i<=n+1; ++i){
while (h[st.top()]<h[i])r[st.top()]=i, st.pop();
l[i]=st.top();
st.push(i);
}
twok.resize(n+2, vector<int>(20));
twokl.resize(n+2, vector<int>(20));
twokr.resize(n+2, vector<int>(20));
twok[0][0]=0;
twok[n+1][0]=n+1;
twokr[n+1][0]=n+1;
twokl[0][0]=0;
for (int i=1; i<=n; ++i){
twokr[i][0]=r[i];
twokl[i][0]=l[i];
if (h[l[i]]>h[r[i]])twok[i][0]=l[i];
else twok[i][0]=r[i];
}
for (int j=1; j<20; ++j)for (int i=0; i<=n+1; ++i)twok[i][j]=twok[twok[i][j-1]][j-1], twokr[i][j]=twokr[twokr[i][j-1]][j-1], twokl[i][j]=twokl[twokl[i][j-1]][j-1];
}
int minimum_jumps(int A, int B, int C, int D){
int a=A+1, b=B+1, c=C+1, d=D+1, node=b, mx=b+1, ans=0;
if (b+1==c)return (twokr[b][0]<=d?1:-1);
for (int i=19; i>=0; --i)if (twokr[mx][i]<=c-1)mx=twokr[mx][i];
if (h[b]>h[mx])return (twokr[b][0]<=d?1:-1);
for (int i=19; i>=0; --i)if (twokl[node][i]>=a&&h[twokl[node][i]]<h[mx])node=twokl[node][i];
if (twokl[node][0]>=a&&twokr[twokl[node][0]][0]<=d)return 1;
if (twokl[node][0]<a){
for (int i=19; i>=0; --i)if (h[twok[node][i]]<=h[mx])node=twok[node][i], ans+=(1<<i);
if (node==mx)return (twokr[node][0]<=d?ans+1:-1);
if (c<=twokr[node][0]&&twokr[node][0]<=d)return ans+1;
if (twokl[node][0]&&c<=twokr[twokl[node][0]][0]&&twokr[twokl[node][0]][0]<=d)return ans+2;
}
for (int i=19; i>=0; --i)if (twokr[node][i]<c)node=twokr[node][i], ans+=(1<<i);
if (c<=twokr[node][0]&&twokr[node][0]<=d)return ans+1;
return -1;
}
