#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int h[200005], l[200005], r[200005], good[20][200005], bad[20][200005], n;
struct node
{
node *lc, *rc;
int l, r;
pair<int, int> val;
node(int l, int r) : lc(0), rc(0), l(l), r(r), val({0, 0}) {}
} *root;
void build(node *i)
{
if (i->l==i->r)
{
i->val={h[i->l], i->l};
return;
}
int mid=(i->l+i->r)/2;
i->lc=new node(i->l, mid);
i->rc=new node(mid+1, i->r);
build(i->lc);
build(i->rc);
i->val=max(i->lc->val, i->rc->val);
}
pair<int, int> query(node *i, int ql, int qr)
{
if (ql<=i->l && i->r<=qr)
return i->val;
int mid=(i->l+i->r)/2;
pair<int, int> ans={0, 0};
if (i->l<=qr && ql<=mid)
ans=max(ans, query(i->lc, ql, qr));
if (mid<qr && ql<=i->r)
ans=max(ans, query(i->rc, ql, qr));
return ans;
}
void init(int N, vector<int> H)
{
n=N;
h[0]=h[n+1]=1e9;
for (int i=1; i<=n; i++)
h[i]=H[i-1];
stack<int> q;
q.push(0);
for (int i=1; i<=n; i++)
{
while (h[q.top()]<h[i])
q.pop();
l[i]=q.top();
q.push(i);
}
while (q.size())
q.pop();
q.push(n+1);
for (int i=n; i; i--)
{
while (h[q.top()]<h[i])
q.pop();
r[i]=q.top();
q.push(i);
}
good[0][n+1]=bad[0][n+1]=n+1;
for (int i=1; i<=n; i++)
{
good[0][i]=h[l[i]]>h[r[i]]?l[i]:r[i];
bad[0][i]=h[l[i]]<h[r[i]]?l[i]:r[i];
}
for (int i=1; i<20; i++)
{
for (int j=0; j<=n+1; j++)
{
good[i][j]=good[i-1][good[i-1][j]];
bad[i][j]=bad[i-1][bad[i-1][j]];
}
}
root=new node(1, n);
build(root);
}
int calc(int u, int v)
{
int ans=0;
for (int i=19; i>=0; i--)
{
if (h[good[i][u]]<=h[v])
{
u=good[i][u];
ans+=1<<i;
}
}
for (int i=19; i>=0; i--)
{
if (h[bad[i][u]]<=h[v])
{
u=bad[i][u];
ans+=1<<i;
}
}
if (u==v)
return ans;
return -1;
}
int minimum_jumps(int a, int b, int c, int d)
{
a++, b++, c++, d++;
pair<int, int> ans1=query(root, c, d);
int l=a, r=b+1;
while (l<r)
{
int mid=(l+r)/2;
pair<int, int> ans2=query(root, mid, b);
if (ans2.first>ans1.first)
l=mid+1;
else
r=mid;
}
if (l==b+1)
return -1;
pair<int, int> ans2=query(root, l, b);
pair<int, int> ans4=(b+2<=c)?query(root, b+1, c-1):make_pair(0, 0);
int ll=c, rr=d;
while (ll<rr)
{
int mid=(ll+rr)/2;
pair<int, int> ans3=query(root, c, mid);
if (max(ans2.first, ans4.first)<ans3.first)
rr=mid;
else
ll=mid+1;
}
pair<int, int> ans3=query(root, c, ll);
int res=calc(ans2.second, ans3.second);
if (l==a)
{
if (ans2.first>ans4.first)
return 1;
int ans=0, u=ans2.second;
for (int i=19; i>=0; i--)
{
if (h[good[i][u]]<ans4.first)
{
u=good[i][u];
ans+=1<<i;
}
}
u=good[0][u];
if (h[u]<ans1.first)
{
ans+=2;
if (res==-1)
res=ans;
else
res=min(res, ans);
}
}
return res;
}
