#include <bits/stdc++.h>
#include "jumps.h"
#define X first
#define Y second
using namespace std;
const int MAXN = 2e5 + 2;
const int LOG = 18;
const int OFF = 1 << LOG + 1;
int n, nxt[MAXN][LOG], prv[MAXN][LOG], nxt_max[MAXN][LOG], prv_max[MAXN][LOG];
pair<int, int> tour[OFF];
vector<int> h;
pair<int, int> f(int x, int l, int r, int ql, int qr){
if(ql > r || l > qr) return {-1, -1};
if(ql <= l && r <= qr) return tour[x];
int mid = (l + r) >> 1;
pair<int, int> L = f(x * 2 + 1, l, mid, ql, qr);
pair<int, int> R = f(x * 2 + 2, mid + 1, r, ql, qr);
return max(L, R);
}
void con(int x, int l, int r){
if(l == r){
tour[x] = {h[l], l};
return ;
}
int mid = (l + r) >> 1;
con(x * 2 + 1, l, mid);
con(x * 2 + 2, mid + 1, r);
tour[x] = max(tour[x * 2 + 1], tour[x * 2 + 2]);
}
void init(int _n, vector<int> _h){
n = _n; h = _h;
con(0, 0, n - 1);
stack<int> s;
for(int i = 0; i < n; ++i){
while(!s.empty() && h[s.top()] < h[i]) s.pop();
if(s.empty()) prv[i][0] = -1;
else prv[i][0] = s.top();
s.push(i);
nxt_max[i][0] = prv_max[i][0] = h[i];
}
while(!s.empty()) s.pop();
for(int i = n - 1; i >= 0; --i){
while(!s.empty() && h[s.top()] < h[i]) s.pop();
if(s.empty()) nxt[i][0] = n;
else nxt[i][0] = s.top();
s.push(i);
}
for(int j = 1; j < LOG; ++j){
for(int i = 0; i < n; ++i){
if(prv[i][j - 1] == -1) prv[i][j] = -1;
else prv[i][j] = prv[prv[i][j - 1]][j - 1];
if(nxt[i][j - 1] == n) nxt[i][j] = n;
else nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
prv_max[i][j] = max(prv_max[i][j - 1], prv_max[max(0, i - (1 << j - 1))][j - 1]);
nxt_max[i][j] = max(nxt_max[i][j - 1], nxt_max[min(n - 1, i + (1 << j - 1))][j - 1]);
}
}
}
int minimum_jumps(int a, int b, int c, int d){
if(max(a, c) <= min(b, d)) return 0;
int ret = 0;
if(b < c){
pair<int, int> maks = f(0, 0, n - 1, b + 1, d);
if(maks.Y < c) return -1;
int idx = b;
for(int i = LOG - 1; i >= 0; --i){
if(idx - (1 << i) >= -1 && prv_max[idx][i] < maks.X){
idx -= 1 << i;
}
}
idx = max(a, idx + 1);
if(idx > b) return -1;
int node = f(0, 0, n - 1, idx, b).Y;
if(a == b){
assert(a == node);
}
for(int i = LOG - 1; i >= 0; --i){
if(nxt[node][i] < c){
node = nxt[node][i];
ret += 1 << i;
}
}
} else {
pair<int, int> maks = f(0, 0, n - 1, c, b - 1);
if(maks.Y > d) return -1;
int idx = a;
for(int i = LOG - 1; i >= 0; --i){
if(idx + (1 << i) <= n && nxt_max[idx][i] < maks.X){
idx += 1 << i;
}
}
idx = min(b, idx - 1);
if(idx < a) return -1;
int node = f(0, 0, n - 1, a, idx).Y;
if(a == b){
assert(a == node);
}
for(int i = LOG - 1; i >= 0; --i){
if(prv[node][i] > d){
node = prv[node][i];
ret += 1 << i;
}
}
}
return ret + 1;
}
