#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define endl '\n'
const int M = 2001, lg = 12;
int dis[M][M][lg], n;
vector<int> nei[M];
void bfs(int u)
{
for (int i=0;i<n;i++) dis[u][i][0]=M;
dis[u][u][0]=0;
queue<int> q;
q.push(u);
while (!q.empty())
{
int x=q.front();q.pop();
for (int i:nei[x])
if (dis[u][i][0]>dis[u][x][0]+1)
{
dis[u][i][0]=dis[u][x][0]+1;
q.push(i);
}
}
}
void init(int N, vector<int> a)
{
n=N;
if (n<=2000)
{
for (int i=0;i<n;i++)
{
for (int j=i-1;j>=0;j--)
if (a[j]>a[i])
{
nei[i].push_back(j);
break;
}
for (int j=i+1;j<n;j++)
if (a[j]>a[i])
{
nei[i].push_back(j);
break;
}
}
for (int i=0;i<n;i++)
{
bfs(i);
for (int j=0;j<n;j++)
for (int p=1;j+(1<<p)<=n;p++)
dis[i][j][p]=min(dis[i][j][p-1],dis[i][j+(1<<p-1)][p-1]);
}
}
}
int get(int a,int l,int r)
{
int b=31-__builtin_clz(r-l);
return min(dis[a][l][b],dis[a][r-(1<<b)][b]);
}
int minimum_jumps(int a,int b,int c,int d)
{
if (n<=2000)
{
int ans=M;
for (int i=a;i<=b;i++)
ans=min(ans,get(i,c,d+1));
if (ans==M) ans=-1;
return ans;
}
return c-b;
}
