#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> mas;
const int dydis = 1e5 + 10;
const int dd = 20;
int mx[dydis][dd];
int lg2[dydis];
void build() {
lg2[1] = 0;
for(int i = 2; i < dydis; i++) lg2[i] = lg2[i/2] + 1;
for(int i = 0; i < n; i++) {
mx[i][0] = mas[i];
}
for(int j = 1; j < dd; j++) {
for(int i = 0; i < n; i++) {
int r = i + (1 << (j-1));
r = min(r, n-1);
mx[i][j] = max(mx[i][j-1], mx[r][j-1]);
}
}
}
vector<int> gr[dydis];
int h[dydis];
void dfs(int v) {
for(auto x : gr[v]) {
h[x] = h[v] + 1;
dfs(x);
}
}
int getMx(int a, int b) {
int pw = lg2[b - a + 1];
// cout << a << "; " << b << " issiskaido i intervala [" << a << "; " << a + (1 << pw) - 1 << "] ir intervala [" << b - (1 << pw) + 1 << "; " << b << "]\n";
int ind = b - (1 << pw) + 1;
return max(mx[a][pw], mx[ind][pw]);
}
int firstLarger[dydis];
int lastLarger[dydis];
void init(int N, vector<int> H) {
n = N ;
mas = H;
build();
set<pair<int, int> > setas;
for(int i = 0; i < n; i++) {
firstLarger[i] = -1;
while(setas.size()) {
if(mas[i] > setas.begin()->first) {
firstLarger[setas.begin()->second] = i;
setas.erase(*setas.begin());
}else break;
}
setas.insert({mas[i], i});
}
setas.clear();
for(int i = n-1; i > -1; i--) {
lastLarger[i] = -1;
while(setas.size()) {
if(mas[i] > setas.begin()->first) {
lastLarger[setas.begin()->second] = i;
setas.erase(*setas.begin());
}else break;
}
setas.insert({mas[i], i});
}
/*
vector<int> roots;
for(int i = 0; i < n; i++) {
if(firstLarger[i] == -1) {
roots.push_back(i);
}else {
gr[firstLarger[i]].push_back(i);
}
}
for(auto x : roots) {
h[x] = 0;
dfs(x);
}*/
for(int i = 0; i < n; i++) {
// cout << "nuo " << i << " is kaires - " << lastLarger[i] << ", o is desines " << firstLarger[i] << endl;
if(lastLarger[i] != -1) gr[i].push_back(lastLarger[i]);
if(firstLarger[i] != -1) gr[i].push_back(firstLarger[i]);
}
}
bool arGalima(int a, int b) { /// ar galima is a i b?
if(mas[a] >= mas[b]) return false;
if(a == b-1) return true;
if(getMx(a+1, b-1) < b) return true;
return false;
}
const int inf = 1e9;
int dist[dydis];
void bfs(int A, int B) {
queue<int> q;
for(int i = 0; i < n; i++) {
dist[i] = inf;
}
for(int i = A; i <= B; i++) {
dist[i] = 0;
q.push(i);
}
while(q.size()) {
int v = q.front();
q.pop();
for(auto x : gr[v]) {
// cout << "is " << v << " galiu eiti i " << x << endl;
if(dist[x] > dist[v] + 1) {
// cout << "nustatau dist[" << x << "] = " << dist[v] + 1 << endl;
dist[x] = dist[v] + 1;
q.push(x);
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
bfs(A, B);
int ret = inf;
for(int i = C; i <= D; i++) {
// cout << "dist[" << i << "
ret = min(ret, dist[i]);
}
if(ret == inf) return -1;
return ret;
// cout << "maximumas tarp " << A << " ir " << C << " yra " << getMx(A, C) << endl;
if(arGalima(A, C) == false) return -1;
return h[A] - h[C];
}
