#if defined(ONPC) && !defined(_GLIBCXX_ASSERTIONS)
#define _GLIBCXX_ASSERTIONS
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include "jumps.h"
#ifdef ONPC
#include "t_debug.cpp"
#else
#define debug(...) 42
#endif
#define allit(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())
using namespace std;
using ll = long long;
using vi = vector<int>;
namespace pd = __gnu_pbds;
template<typename K>
using ordered_set = pd::tree<K, pd::null_type, less<int>, pd::rb_tree_tag, pd::tree_order_statistics_node_update>;
template<typename... T>
using gp_hash_table = pd::gp_hash_table<T...>;//simple using statement gives warnings
const int INF = 1e9;
const ll INFL = 1e18;
const int N = 100000;
const int LOGN = 17;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);
int subtask;
struct SegTree {
int n;
vi tree;
SegTree(int n_) : n(n_), tree(2*n_, INF) {}
inline void set(int i, int v) {tree[n+i] = min(tree[n+i], v);}
inline int get(int i) {return tree[n+i];}
void calc() {
for (int i = n-1; i >= 1; i--) {
tree[i] = min(tree[2*i], tree[2*i+1]);
}
}
int query(int l, int r) {
l += n;
r += n;
int res = INF;
while (l <= r) {
if (l % 2 == 1) res = min(res, tree[l++]);
if (r % 2 == 0) res = min(res, tree[r--]);
l /= 2;
r /= 2;
}
return res;
}
void update(int i, int v) {
tree[n+i] = v;
for (i = (i+n) / 2; i >= 1; i /= 2) {
tree[i] = min(tree[2*i], tree[2*i+1]);
}
}
void print() {
for (int i = n; i < 2*n; i++) {
if (tree[i] == INF) printf(" #");
else printf("%3d", tree[i]);
}
cout << endl;
}
};
int next_power2(int i) {
i--;
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
return 1+i;
}
vector<vi> adj;
int dist[2000][2000];
int dfs(int i, int j) {
if (i == j) return 0;
if (dist[i][j] != 0) return dist[i][j];
int res = INF;
for (int e : adj[i]) {
res = min(res, 1+dfs(e, j));
}
dist[i][j] = res;
return res;
}
void init_2_3(int n, vi& h) {
adj.resize(n);
vi root(n, 1);
memset(dist, 0, sizeof(dist));
for (int i = 0; i < n; i++) {
int j = i-1, k = i+1;
for (; j >= 0; j--) {
if (h[j] > h[i]) break;
}
for (; k < n; k++) {
if (h[k] > h[i]) break;
}
if (j >= 0) {
adj[i].push_back(j);
root[j] = 0;
}
if (k < n) {
adj[i].push_back(k);
root[k] = 0;
}
}
}
int minimum_jumps_2_3(int a, int b, int c, int d) {
int res = INF;
for (int i = a; i <= b; i++) {
for (int j = c; j <= d; j++) {
res = min(res, dfs(i, j));
}
}
return (res < INF ? res : -1);
}
vi h;
int st_high[N][LOGN], st_low[N][LOGN];
int to_j;
void init_4_5_6(int n, vi& h_) {
h = h_;
to_j = __builtin_ctz(next_power2(n));
adj.resize(n);
stack<int> prev;
for (int i = 0; i < n; i++) {
while (!prev.empty() && h[prev.top()] < h[i]) {
adj[prev.top()].push_back(i);
prev.pop();
}
prev.push(i);
}
while (!prev.empty()) prev.pop();
for (int i = n-1; i >= 0; i--) {
while (!prev.empty() && h[prev.top()] < h[i]) {
adj[prev.top()].push_back(i);
prev.pop();
}
prev.push(i);
}
for (int i = 0; i < n; i++) {
if (adj[i].size() == 2 && h[adj[i][0]] > h[adj[i][1]]) {
swap(adj[i][0], adj[i][1]);
}
}
debug(adj);
for (int i = 0; i < N; i++) {
for (int j = 0; j < LOGN; j++) {
st_high[i][j] = st_low[i][j] = -1;
}
}
for (int i = 0; i < n; i++) {
if (adj[i].size() == 2) {
st_high[i][0] = adj[i][1];
st_low[i][0] = adj[i][0];
} else if (adj[i].size() == 1) {
st_high[i][0] = st_low[i][0] = adj[i][0];
}
}
for (int j = 1; j < LOGN; j++) {
for (int i = 0; i + (1 <<j) < n; i++) {
int next = st_high[i][j-1];
if (next !=-1)
st_high[i][j] = st_high[next][j-1];
next = st_low[i][j-1];
if (next != -1)
st_low[i][j] = st_low[ st_low[i][j-1] ][j-1];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < to_j; j++) {
cout << st_high[i][j] << ',' << st_low[i][j] << '\t';
}
cout << endl;
}
}
int minimum_jumps_4(int a, int b, int c, int d) {
queue<pair<int,int>> q;
vector<char> visited(adj.size());
for (int i = a; i <= b; i++)
q.push({i, 0});
int res = -1;
while (!q.empty()) {
auto [cur, depth] = q.front();
q.pop();
if (c <= cur && cur <= d) {
res = depth;
break;
}
for (int e : adj[cur])
if (!visited[e]) {
q.push({e, depth+1});
visited[e] = 1;
}
}
return res;
}
int minimum_jumps_5(int a, int b, int c, int d) {
debug(5);
assert(a == b);
assert(c == d);
int res = 0, cur = a;
for (int j = to_j-1; j >= 0; j--) {
if (st_high[cur][j] != -1 && h[st_high[cur][j]] <= h[c]) {
res += 1<<j;
cur = st_high[cur][j];
}
}
for (int j =to_j-1; j >= 0; j--) {
if (st_low[cur][j] != -1 && h[st_low[cur][j]] <= h[c]) {
res += 1<<j;
cur = st_low[cur][j];
}
}
return cur == d ? res : -1;
}
void init(int n, std::vector<int> h) {
int inc = 1;
for (int i = 1; i < n; i++) inc &= h[i-1] < h[i];
if (inc) {
subtask = 1;
} else if (n <= 2000) {
subtask = 2;
init_2_3(n, h);
} else {
subtask = 4;
init_4_5_6(n, h);
}
debug(subtask);
}
int minimum_jumps(int a, int b, int c, int d) {
if (subtask == 2)
return minimum_jumps_2_3(a,b,c,d);
else if (subtask == 4) {
if (a == b && c == d)
return minimum_jumps_5(a,b,c,d);
else
return minimum_jumps_4(a,b,c,d);
}
else return c - b;
}
