#include "jump.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n, par[ 200001 ][ 21 ], parr[ 200001 ][ 21 ], dist[ 200001 ][ 21 ], distt[ 200001 ][ 21 ];
int lg = 20;
int a[ 200001 ], l[ 200001 ], r[ 200001 ], sum = 0;
vector <int> v[ 200001 ], vv;
vector <pair<int, int> > v1;
bool ok;
void init(int N, vector<int> H) {
n = N;
for ( int i = 0 ; i < H.size(); i ++ ) {
a[ i + 1 ] = H[ i ];
v1.push_back( { a[ i + 1 ], i + 1 } );
}
sort( v1.begin(), v1.end() );
for ( int i = 1; i <= n; i ++ ) {
while ( vv.size() && a[ vv.back() ] < a[ i ] ) {
vv.pop_back();
}
if ( vv.size() ) {
v[ i ].push_back( vv.back() );
}
vv.push_back( i );
}
vv.clear();
for ( int i = n; i >= 1; i -- ) {
while ( vv.size() && a[ vv.back() ] < a[ i ] ) {
vv.pop_back();
}
if ( vv.size() )
v[ i ].push_back( vv.back() );
vv.push_back( i );
}
for ( int i = 1; i <= n; i ++ ) {
if ( v[ i ].size() == 1 ) {
parr[ i ][ 0 ] = v[ i ].back();
par[ i ][ 0 ] = i;
dist[ i ][ 0 ] = 0;
distt[ i ][ 0 ] = 1;
}
else if ( v[ i ].size() == 2 ) {
if ( a[ v[ i ].back() ] > a[ v[ i ].front() ] ) {
par[ i ][ 0 ] = v[ i ].back();
parr[ i ][ 0 ] = v[ i ].front();
}
else {
par[ i ][ 0 ] = v[ i ].front();
parr[ i ][ 0 ] = v[ i ].back();
}
dist[ i][ 0 ] = distt[ i ][ 0 ] = 1;
}
else {
par[ i ][ 0 ] = parr[ i ][ 0 ] = i;
dist[ i ][ 0 ] = distt[ i ][ 0 ] = 0;
}
}
for ( int i = v1.size() - 1; i >= 0; i -- ) {
for ( int j = 1; j <= lg; j ++ ) {
par[ v1[ i ].second ][ j ] = par[ par[ v1[ i ].second ][ j - 1 ]][ j - 1 ];
dist[ v1[ i ].second ][ j ] = dist[ par[ v1[ i ].second ][ j - 1 ] ][ j - 1 ] + dist[ v1[ i ].second ][ j - 1 ];
parr[ v1[ i ].second ][ j ] = parr[ parr[ v1[ i ].second ][ j - 1 ] ][ j - 1 ];
distt[ v1[ i ].second ][ j ] = distt[ parr[ v1[ i ].second ][ j - 1 ] ][ j - 1 ] + distt[ v1[ i ].second ][ j - 1 ];
}
}
for ( int i = n; i > 1; i -- ) {
if ( a[ i ] <= a[ i - 1 ] )
ok = 1;
}
}
const long long oo = 1e18;
long long mx, mn;
int c, f;
map <int, long long> d;
map <int, bool> used;
queue <int> q;
long long int bfs() {
mx = oo;
while ( q.size() ) {
int g = q.front();
q.pop();
for ( auto to : v[ g ] ) {
if ( !used[ to ] || d[ to ] > d[ g ] + 1 ) {
d[ to ] = d[ g ] + 1;
q.push( to );
if ( to >= c && to <= f ) {
mx = min( d[ g ] + 1, mx );
}
used[ to ] = 1;
}
}
}
while( q.size() )
q.pop();
return mx;
}
pair<int,int> lca( int aa, int b ) {
int sum = 0;
if ( aa == b )
return { aa, 0 };
for ( int i = lg; i >= 0; i -- ) {
if ( a[ par[ aa ][ i ] ] <= a[ b ] ) {
sum += dist[ aa ][ i ];
aa = par[ aa ][ i ];
}
}
return { aa, sum };
}
pair<int,int> lca1( int aa, int b ) {
if ( aa == b )
return { aa, 0 };
int sum = 0;
for ( int i = lg; i >= 0; i -- ) {
if ( a[ parr[ aa ][ i ] ] < a[ b ] ) {
sum += distt[ aa ][ i ];
aa = parr[ aa ][ i ];
}
}
return { parr[ aa ][ 0 ], sum + distt[ aa ][ 0 ] };
}
int minimum_jumps(int A, int B, int C, int D) {
A ++;
B ++;
C ++;
D ++;
if ( !ok ) {
if ( C > B )
return C - B;
else
return A - D;
}
if ( A == B && C == D ) {
pair<int, int> p;
p = lca( A, C );
sum = p.second;
p = lca1( p.first, C );
if ( p.first == C )
return sum + p.second;
return -1;
}
d.clear();
used.clear();
c = C;
f = D;
mn = oo;
for ( int i = A; i <= B; i ++ ) {
q.push( i );
used[ i ] = 1;
}
mn = bfs( );
if ( mn == oo )
return -1;
return mn;
}
//int main () {
// int n;
// cin >> n;
// int a;
// vector <int> v;
// v.clear();
// for ( int i = 1; i <= n; i ++ )
// cin >> a, v.push_back( a );
// init( n, v );
// int m, a, b, c, d;
// cin >> m;
// while ( m -- ) {
// cin >> a >> b >> c >> d;
//
// }
//}
