#include <vector> // For std::vector
#include <queue> // For std::queue
#include <stack> // For std::stack
#include <algorithm> // For std::min
#include <limits> // For std::numeric_limits
// Global variables to store tree information and precomputed data
int N_global; // Number of trees
std::vector<int> H_global; // Heights of the trees
// L[i]: index of the nearest tree to the left of 'i' with height > H[i]. -1 if no such tree exists. [cite: 5]
// R[i]: index of the nearest tree to the right of 'i' with height > H[i]. -1 if no such tree exists. [cite: 6]
std::vector<int> L, R;
// Reversed graph adjacency list. [cite: 5, 6]
// rev_adj[j] contains all indices 'i' such that the orangutan can jump FROM 'i' TO 'j'.
// This is used for the backward BFS.
std::vector<std::vector<int>> rev_adj;
// Define a constant for infinity, used for unreachable nodes in BFS.
const int INF = std::numeric_limits<int>::max();
/**
* @brief Preprocessing function called once before any queries.
*
* Calculates the possible jump destinations (L[i] and R[i]) for each tree 'i'
* using monotonic stacks.
* Builds the reversed graph representation needed for backward BFS.
* Complexity: O(N)
*
* @param N The number of trees. [cite: 9]
* @param H A vector containing the heights of the N trees. [cite: 10]
*/
void init(int N, std::vector<int> H) {
N_global = N;
H_global = H; // Store N and H globally for access in minimum_jumps
L.assign(N, -1); // Initialize left jump targets to -1 (no jump)
R.assign(N, -1); // Initialize right jump targets to -1
rev_adj.assign(N, std::vector<int>()); // Initialize the reversed adjacency list
// --- Calculate L[i] (nearest taller tree to the left) ---
std::stack<int> st_left; // Monotonic stack storing indices in decreasing height order
for (int i = 0; i < N; ++i) {
// Pop elements from the stack that are shorter than or equal to the current tree H[i]
// Ensures the stack top (if exists) is the nearest element to the left *taller* than H[i]
while (!st_left.empty() && H[st_left.top()] <= H[i]) {
st_left.pop();
}
// If the stack is not empty, the top element is the target L[i]
if (!st_left.empty()) {
L[i] = st_left.top();
}
// Push the current tree index onto the stack
st_left.push(i);
}
// --- Calculate R[i] (nearest taller tree to the right) ---
std::stack<int> st_right; // Monotonic stack
for (int i = N - 1; i >= 0; --i) { // Iterate from right to left
// Pop elements shorter than or equal to H[i]
while (!st_right.empty() && H[st_right.top()] <= H[i]) {
st_right.pop();
}
// If stack not empty, top is the target R[i]
if (!st_right.empty()) {
R[i] = st_right.top();
}
// Push current index
st_right.push(i);
}
// --- Build the reversed graph adjacency list `rev_adj` ---
// For each possible jump i -> L[i] or i -> R[i] in the original graph,
// add a corresponding reversed edge L[i] -> i or R[i] -> i to rev_adj.
for (int i = 0; i < N; ++i) {
if (L[i] != -1) {
// If a jump from i to L[i] is possible, add edge L[i] -> i in reversed graph
rev_adj[L[i]].push_back(i);
}
if (R[i] != -1) {
// If a jump from i to R[i] is possible, add edge R[i] -> i in reversed graph
rev_adj[R[i]].push_back(i);
}
}
}
/**
* @brief Calculates the minimum number of jumps required.
*
* Finds the minimum jumps needed to get from any starting tree 's' in the range [A, B]
* to any ending tree 'e' in the range [C, D]. [cite: 7, 8]
* Uses Breadth-First Search (BFS) starting *backwards* from the target range [C, D]
* on the reversed graph.
* Complexity: O(N) per query, as BFS visits each node/edge at most once.
*
* @param A The start index of the starting range. [cite: 12]
* @param B The end index of the starting range. [cite: 12]
* @param C The start index of the ending range. [cite: 13]
* @param D The end index of the ending range. [cite: 13]
* @return The minimum number of jumps, or -1 if it's impossible. [cite: 14]
*/
int minimum_jumps(int A, int B, int C, int D) {
// 'd[i]' will store the minimum jumps from tree 'i' to *any* tree in the range [C, D].
std::vector<int> d(N_global, INF); // Initialize distances to infinity
std::queue<int> q; // Queue for BFS
// --- Initialize BFS ---
// Start BFS from all trees in the target range [C, D].
// Set their distance to 0 and add them to the queue.
for (int i = C; i <= D; ++i) {
// Check if already initialized (d[i] might be set if C=D and the node is added multiple times, though loop structure prevents this)
if (d[i] == INF) {
d[i] = 0; // Distance from a target node to the target set is 0
q.push(i); // Add to BFS queue
}
}
// --- Perform Backward BFS ---
// Explore the graph using the reversed edges (rev_adj).
while (!q.empty()) {
int u = q.front(); // Current node being processed
q.pop();
// Iterate through all nodes 'v' that can jump *to* 'u' in the original graph
// (represented by edges u -> v in the reversed graph)
for (int v : rev_adj[u]) {
// If node 'v' has not been reached yet (distance is INF)
if (d[v] == INF) {
// Update the distance to 'v' (one more jump than distance to 'u')
d[v] = d[u] + 1;
// Add 'v' to the queue to explore its predecessors
q.push(v);
}
}
}
// --- Find the minimum jumps from the starting range [A, B] ---
int min_jumps = INF; // Initialize minimum jumps found so far
// Iterate through all possible starting trees 's' in the range [A, B]
for (int i = A; i <= B; ++i) {
// If tree 'i' can reach the target range (d[i] is not INF)
if (d[i] != INF) {
// Update the overall minimum jumps if the path from 'i' is shorter
min_jumps = std::min(min_jumps, d[i]);
}
}
// --- Return the result ---
// If min_jumps is still INF, no path exists from [A, B] to [C, D]
if (min_jumps == INF) {
return -1; // Impossible [cite: 14, 21]
} else {
// Otherwise, return the minimum number of jumps found [cite: 8]
return min_jumps;
}
}
