#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define size(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int wiel = 1024*512-1;
pii drzewo[wiel];
pii query_t(int akt, int p1, int p2, int s1, int s2)
{
if(s1 > s2) return {-1,-1};
if(p2 < s1 || p1 > s2) return {-1,-1};
if(p1 >= s1 && p2 <= s2) return drzewo[akt-1];
return max(query_t(akt*2,p1,(p1+p2)/2,s1,s2),query_t(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
int next_[200001];
int prev_[200001];
int jump[200001][20];
int jump2[200001][20];
int h[200001];
int n;
bool subtask1 = true;
void init(int N, vector<int> H)
{
h[n] = 1e9;
n = N;
rep(i,n) h[i] = H[i];
rep(i,n) drzewo[wiel/2+i] = {h[i],i};
rep2(i,wiel/2 +n,wiel-1) drzewo[i] = {-1,-1};
for(int i = wiel/2-1; i >= 0; i--)
{
drzewo[i] = max(drzewo[i*2+1],drzewo[i*2+2]);
}
vector<pii> q;
rep(i,n)
{
if(i != 0)
{
if(h[i] < h[i-1]) subtask1 = false;
}
while(size(q) > 0 && h[i] > q.back().ff) q.pop_back();
if(size(q) != 0)
{
prev_[i] = q.back().ss;
}
else prev_[i] = n;
q.pb({h[i],i});
}
q = {};
for(int i = n-1; i >= 0; i--)
{
while(size(q) > 0 && h[i] > q.back().ff) q.pop_back();
if(size(q) != 0)
{
next_[i] = q.back().ss;
}
else next_[i] = n;
q.pb({h[i],i});
}
rep(i,n)
{
if(h[next_[i]] < h[prev_[i]])
{
swap(next_[i],prev_[i]);
}
// cerr << i << " " << next_[i] << " " << prev_[i] << " nx prv\n";
jump[i][0] = next_[i];
if(prev_[i] != i) jump2[i][0] = prev_[i];
else jump2[i][0] = next_[i];
}
jump[n][0] = n;
jump2[n][0] = n;
rep2(bit,1,19)
{
rep(i,n+1)
{
jump[i][bit] = jump[jump[i][bit-1]][bit-1];
}
}
rep2(bit,1,19)
{
rep(i,n+1)
{
jump2[i][bit] = jump2[jump2[i][bit-1]][bit-1];
}
}
h[n] = 1e9;
}
int minimum_jumps(int A, int B, int C, int D) {
if(A <= C && C <= B) return 0;
if(A <= D && D <= B) return 0;
if(C <= A && A <= D) return 0;
if(C <= B && B <= D) return 0;
int maxsrod = query_t(1,0,wiel/2,B+1,C-1).ff;
if(A > C) maxsrod = query_t(1,0,wiel/2,D+1,A-1).ff;
int maxkon = query_t(1,0,wiel/2,C,D).ff;
if(maxkon < maxsrod) return -1;
// cerr << maxsrod << " maxsrod\n";
// if(A < C) if(maxsrod > query_t(1,0,wiel/2,0,B).ff) return -1;
// else if(maxsrod > query_t(1,0,wiel/2,A,n-1).ff) return -1;
int start = A;
int domh = h[C];
if(C > B)
{
int pocz = A;
int kon = B;
start = B;
while(pocz <= kon)
{
int srod = (pocz+kon)/2;
if(query_t(1,0,wiel/2,srod,B).ff < maxkon)
{
start = srod;
kon = srod-1;
}
else pocz = srod+1;
}
start = query_t(1,0,wiel/2,start,B).ss;
if(start == -1) return -1;
}
else
{
domh = h[D];
int pocz = A;
int kon = B;
start = A;
while(pocz <= kon)
{
int srod = (pocz+kon)/2;
if(query_t(1,0,wiel/2,A,srod).ff < maxkon)
{
start = srod;
pocz = srod+1;
}
else kon = srod-1;
}
//cerr << start << " " << query_t(1,0,wiel/2,A,start).ff << " " << h[C] << " ans\n";
start = query_t(1,0,wiel/2,A,start).ss;
if(start == -1) return -1;
}
int ans = 0;
cerr << start << " start\n";
if(h[start] > maxkon) return -1;
for(int bit = 19; bit >= 0; bit--)
{
if(h[jump[start][bit]] <= maxsrod)
{
start = jump[start][bit];
ans += (1 << bit);
}
}
if(h[jump[start][0]] <= maxkon)
{
start = jump[start][0];
ans++;
}
if(A < C && start >= C) return ans;
if(A > C && start <= D) return ans;
cerr << h[start] << " "<< start << " " << ans << " " << jump[start][0] << " " << jump2[start][0]<< " start\n";
for(int bit = 19; bit >= 0; bit--)
{
if(h[jump[start][bit]] <= domh)
{
start = jump[start][bit];
ans += (1 << bit);
}
}
if(h[start] == domh) return ans;
cerr << h[start] << " "<< start << " " << ans << " " << jump[start][0] << " " << jump2[start][0]<< " start\n";
for(int bit = 19; bit >= 0; bit--)
{
if(h[jump2[start][bit]] < domh)
{
start = jump2[start][bit];
ans += (1 << bit);
}
}
cerr << start << " " << ans << " start\n";
return ans+1;
}
