P15130 [ROIR 2026] Super Jump

In the computer game "Super Jump", the hero jumps between the peaks of mountains. The goal is to reach the position with a flag and complete the level there. The mountain range in the game consists of $n$ serrated peaks arranged consecutively. The $i$-th peak is located at position $i$ and has height $h_i$. For any $i < j$, the hero can jump in a straight line from peak $i$ to peak $j$ if the flight path does not meet any other peak. More formally, there is no $k$ such that $i < k < j$ and the вершина (dingdian) of the $k$-th peak—the point with coordinates $(k, h_k)$—is strictly higher than the line segment connecting $(i, h_i)$ and $(j, h_j)$. "Beat AI" is training a neural network to control the hero in the game. To create training data, they need to answer multiple queries: for a pair of indices $l, r$ ($1 \leq l \leq r \leq n$), determine the minimum number of jumps required for the hero to reach peak $r$ starting from peak $l$.

The first line of the input contains a number $n$ ($1 \leq n \leq 10^5$) — the number of peaks. The second line contains $n$ numbers: $h_1, h_2, \ldots, h_n$ ($0 \leq h_i \leq 10^{12}$) — the heights of the peaks. The third line contains a number $q$ ($1 \leq q \leq 10^5$) — the number of queries. Each of the next $q$ lines contains two numbers $l_i, r_i$ ($1 \leq l_i \leq r_i \leq n$) — the parameters of each query.

For each query, output a non-negative integer on a separate line — the minimum number of jumps required.

### Sample Explanation We analyze the second query in the sample. The path for the hero from peak 2 to peak 7 can look as follows: :::align{center}  ::: He will visit peaks 2, 5, and 7 in order, making a total of two jumps. ### Scoring Rules | Subtask | Points | Additional Constraints | Required Subtasks | |:-:|:-:|:-:|:-:| | 1 | 9 | $n, q \leq 300$ | | | 2 | 9 | $n, q \leq 5000$ | 1 | | 3 | 14 | $h_i \leq 10$ | | | 4 | 21 | There exists $k$ such that for all $i$, $l_i \leq k \leq r_i$ | | | 5 | 27 | $n, q \leq 5 \cdot 10^4$ | 1, 2 | | 6 | 20 | No additional constraints | 1–5 | Translated by ChatGPT 5