#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int seg[800005], dist[200005], n;
vector<int> adj[200005];
queue<int> q;
void build(int i, int l, int r)
{
if (l==r)
{
seg[i]=-1;
return;
}
int mid=(l+r)/2;
build(i*2, l, mid);
build(i*2+1, mid+1, r);
seg[i]=-1;
}
void build2(int i, int l, int r)
{
if (l==r)
{
seg[i]=1e9;
return;
}
int mid=(l+r)/2;
build2(i*2, l, mid);
build2(i*2+1, mid+1, r);
seg[i]=1e9;
}
void upd(int i, int l, int r, int x, int y)
{
if (l==r)
{
seg[i]=y;
return;
}
int mid=(l+r)/2;
if (x<=mid)
upd(i*2, l, mid, x, y);
else
upd(i*2+1, mid+1, r, x, y);
seg[i]=y;
}
void upd2(int i, int l, int r, int x, int y)
{
if (l==r)
{
seg[i]=y;
return;
}
int mid=(l+r)/2;
if (x<=mid)
upd2(i*2, l, mid, x, y);
else
upd2(i*2+1, mid+1, r, x, y);
seg[i]=y;
}
int qry(int i, int l, int r, int ql, int qr)
{
if (ql<=l && r<=qr)
return seg[i];
int mid=(l+r)/2, res=-1;
if (l<=qr && ql<=mid)
res=max(res, qry(i*2, l, mid, ql, qr));
if (mid<qr && ql<=r)
res=max(res, qry(i*2+1, mid+1, r, ql, qr));
return res;
}
int qry2(int i, int l, int r, int ql, int qr)
{
if (ql<=l && r<=qr)
return seg[i];
int mid=(l+r)/2, res=1e9;
if (l<=qr && ql<=mid)
res=min(res, qry2(i*2, l, mid, ql, qr));
if (mid<qr && ql<=r)
res=min(res, qry2(i*2+1, mid+1, r, ql, qr));
return res;
}
void init(int nn, vector<int> h)
{
n=nn;
build(1, 1, n);
for (int i=0; i<n; i++)
{
int res=(h[i]==n?-1:qry(1, 1, n, h[i]+1, n));
if (res!=-1)
adj[i].push_back(res);
upd(1, 1, n, h[i], i);
}
build2(1, 1, n);
for (int i=n-1; i>=0; i--)
{
int res=(h[i]==n?1e9:qry2(1, 1, n, h[i]+1, n));
if (res!=1e9)
adj[i].push_back(res);
upd2(1, 1, n, h[i], i);
}
}
int minimum_jumps(int a, int b, int c, int d)
{
for (int i=0; i<n; i++)
dist[i]=1e9;
for (int i=a; i<=b; i++)
{
dist[i]=0;
q.push(i);
}
while (!q.empty())
{
int u=q.front();
q.pop();
for (int v:adj[u])
{
if (dist[u]+1<dist[v])
{
dist[v]=dist[u]+1;
q.push(v);
}
}
}
int ans=1e9;
for (int i=c; i<=d; i++)
ans=min(ans, dist[i]);
return (ans<5e8?ans:-1);
}
