#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10, maxlog = 21;
int n, h[maxn], left_child[maxn], right_child[maxn];
int dp[maxlog][maxn], fp[maxlog][maxn];
bool sorted;
struct node
{
int mx, pos;
node(int _mx = 0, int _pos = 0)
{
mx = _mx;
pos = _pos;
}
};
node merge_node(node lf, node rf)
{
node nd;
if (lf.mx > rf.mx)
nd = lf;
else
nd = rf;
return nd;
}
node tree[4 * maxn];
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root].mx = h[left];
tree[root].pos = left;
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return node();
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_node(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
int walk(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft || tree[root].mx < val)
return qleft - 1;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
if (tree[root * 2 + 1].mx > val)
return walk(root * 2 + 1, mid + 1, right, qleft, qright, val);
return walk(root * 2, left, mid, qleft, qright, val);
}
return max(walk(root * 2, left, mid, qleft, qright, val),
walk(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
void init(int N, vector<int> H)
{
n = N;
for (int i = 0; i < N; i ++)
{
left_child[i + 1] = right_child[i + 1] = 0;
h[i + 1] = H[i];
}
sorted = true;
for (int i = 1; i <= N; i ++)
if (h[i] < h[i - 1])
sorted = false;
stack < int > st;
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && h[i] > h[st.top()])
st.pop();
if (!st.empty())
left_child[i] = st.top();
st.push(i);
}
while(!st.empty())
st.pop();
for (int i = n; i > 0; i --)
{
while(!st.empty() && h[i] > h[st.top()])
st.pop();
if (!st.empty())
right_child[i] = st.top();
st.push(i);
}
h[0] = 1e9;
for (int i = 1; i <= n; i ++)
{
if (h[left_child[i]] > h[right_child[i]])
dp[0][i] = left_child[i];
else
dp[0][i] = right_child[i];
fp[0][i] = right_child[i];
}
for (int j = 1; j < maxlog; j ++)
for (int i = 1; i <= n; i ++)
{
dp[j][i] = dp[j - 1][dp[j - 1][i]];
fp[j][i] = fp[j - 1][fp[j - 1][i]];
}
build_tree(1, 1, n);
}
int used[maxn];
int minimum_jumps(int A, int B, int C, int D)
{
if (sorted)
return C - B;
A ++;
B ++;
C ++;
D ++;
if (A == B && C == D)
{
int ver = A, ans = 0;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (h[dp[bit][ver]] < h[C])
{
ans = ans + (1 << bit);
ver = dp[bit][ver];
}
}
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (h[fp[bit][ver]] < h[C])
{
ans = ans + (1 << bit);
ver = fp[bit][ver];
}
}
if (right_child[ver] == C)
return ans + 1;
return -1;
}
if (C == D)
{
int gt = walk(1, 1, n, A, B, h[C]);
int pos = -1;
if (gt != B)
{
node cur = query(1, 1, n, gt + 1, B);
pos = cur.pos;
}
/**for (int i = B; i >= A; i --)
{
if (h[i] > h[C])
break;
if (pos == -1 || h[i] > h[pos])
pos = i;
}*/
if (pos == -1)
return -1;
///cout << pos << " : " << h[pos] << " : "<< h[C] << endl;
int ver = pos, ans = 0;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (h[dp[bit][ver]] < h[C])
{
ans = ans + (1 << bit);
ver = dp[bit][ver];
}
}
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (h[fp[bit][ver]] < h[C])
{
ans = ans + (1 << bit);
ver = fp[bit][ver];
}
}
///cout << "here " << ver << " " << right_child[ver] << " " << h[right_child[ver]] << endl;
if (right_child[ver] == C)
return ans + 1;
return -1;
}
int ans = 1e9;
for (int i = 1; i <= n; i ++)
used[i] = 0;
queue < int > q;
for (int i = A; i <= B; i ++)
{
q.push(i);
used[i] = 1;
}
//cout << "------------" << endl;
while(!q.empty())
{
int cur = q.front();
q.pop();
///cout << cur << endl;
if (left_child[cur] != 0 && used[left_child[cur]] == 0)
{
used[left_child[cur]] = used[cur] + 1;
q.push(left_child[cur]);
}
if (right_child[cur] != 0 && used[right_child[cur]] == 0)
{
used[right_child[cur]] = used[cur] + 1;
q.push(right_child[cur]);
}
}
for (int to = C; to <= D; to ++)
{
///cout << "here "<< to << " " << used[to] << endl;
if (used[to] != 0)
{
ans = min(ans, used[to] - 1);
}
}
if (ans == 1e9)
return -1;
return ans;
}
