#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
#include <numeric> // Required potentially, though not used in final version
// Global variables
int N_global;
std::vector<int> H_global;
std::vector<int> L, R;
std::vector<std::vector<int>> rev_adj;
// Flag to check if the input matches the specific conditions of Subtask 1
bool is_subtask1 = false;
// Define a constant for infinity, used for unreachable nodes in BFS.
const int INF = std::numeric_limits<int>::max();
/**
* @brief Helper function to check if the height array corresponds to Subtask 1.
* In Subtask 1, H[i] = i + 1 for all i from 0 to N-1.
* Complexity: O(N)
*
* @param N The number of trees.
* @param H The vector containing tree heights.
* @return True if H[i] = i + 1 for all i, False otherwise.
*/
bool check_subtask1(int N, const std::vector<int>& H) {
if (H.size() != N) return false; // Basic sanity check
for (int i = 0; i < N; ++i) {
// The problem statement defines heights starting from 1.
// H[i] = i + 1 means heights are 1, 2, 3, ..., N.
if (H[i] != i + 1) {
return false; // If any height doesn't match, it's not Subtask 1
}
}
// If all heights match H[i] = i + 1, it's Subtask 1
return true;
}
/**
* @brief Preprocessing function called once before any queries.
*
* Checks if the input matches Subtask 1.
* If not Subtask 1, calculates jump targets (L[i], R[i]) using monotonic stacks
* and builds the reversed graph representation.
* Complexity: O(N)
*
* @param N The number of trees.
* @param H A vector containing the heights of the N trees.
*/
void init(int N, std::vector<int> H) {
N_global = N;
H_global = H;
L.assign(N, -1);
R.assign(N, -1);
rev_adj.assign(N, std::vector<int>());
// Check for the Subtask 1 special case (H[i] = i + 1)
is_subtask1 = check_subtask1(N, H);
// If it is Subtask 1, we can skip the general L, R, and rev_adj computation
// because minimum_jumps can compute the answer directly in O(1).
if (is_subtask1) {
return;
}
// --- Calculate L[i] (nearest taller tree to the left) --- Not needed if Subtask 1
std::stack<int> st_left;
for (int i = 0; i < N; ++i) {
while (!st_left.empty() && H[st_left.top()] <= H[i]) {
st_left.pop();
}
if (!st_left.empty()) {
L[i] = st_left.top();
}
st_left.push(i);
}
// --- Calculate R[i] (nearest taller tree to the right) --- Not needed if Subtask 1
std::stack<int> st_right;
for (int i = N - 1; i >= 0; --i) {
while (!st_right.empty() && H[st_right.top()] <= H[i]) {
st_right.pop();
}
if (!st_right.empty()) {
R[i] = st_right.top();
}
st_right.push(i);
}
// --- Build the reversed graph `rev_adj` --- Not needed if Subtask 1
for (int i = 0; i < N; ++i) {
if (L[i] != -1) {
rev_adj[L[i]].push_back(i);
}
if (R[i] != -1) {
rev_adj[R[i]].push_back(i);
}
}
}
/**
* @brief Calculates the minimum number of jumps required.
*
* Handles Subtask 1 (H[i]=i+1) as a special case for O(1) query time.
* For other cases, uses the O(N) backward BFS approach per query.
*
* @param A Start index of the starting range [A, B].
* @param B End index of the starting range [A, B].
* @param C Start index of the ending range [C, D].
* @param D End index of the ending range [C, D].
* @return The minimum number of jumps, or -1 if impossible.
*/
int minimum_jumps(int A, int B, int C, int D) {
// --- Handle Subtask 1 Special Case ---
if (is_subtask1) {
// In this case, jumps are always i -> i+1.
// The graph is a simple path 0 -> 1 -> ... -> N-1.
// The distance dist(s, e) is simply e - s (if s <= e).
// We need min(e - s) for s in [A, B] and e in [C, D].
// Since the problem guarantees B < C, we always have s <= B < C <= e, so s < e.
// To minimize e - s, we maximize s (take s = B) and minimize e (take e = C).
// The minimum number of jumps is C - B.
return C - B;
}
// --- General Case: Backward BFS ---
// (This part remains O(N) per query and is likely too slow for large N/Q in subtasks 5, 6, 7)
std::vector<int> d(N_global, INF);
std::queue<int> q;
// Initialize BFS from the target range [C, D]
for (int i = C; i <= D; ++i) {
if (d[i] == INF) {
d[i] = 0;
q.push(i);
}
}
// Perform BFS on the reversed graph
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : rev_adj[u]) { // Explore nodes 'v' that can jump TO 'u'
if (d[v] == INF) { // If 'v' is unvisited
d[v] = d[u] + 1; // Update distance
q.push(v); // Add to queue
}
}
}
// Find the minimum distance from the starting range [A, B]
int min_jumps = INF;
for (int i = A; i <= B; ++i) {
if (d[i] != INF) { // Check if reachable
min_jumps = std::min(min_jumps, d[i]);
}
}
// Return result
if (min_jumps == INF) {
return -1; // Impossible
} else {
return min_jumps; // Minimum jumps found
}
}
