Problem Description

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$.

Input Format

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.

Output Format

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

8
5 3 4 3 6 2 1 4
3
1 8
2 7
4 4

2
2
0

Hint

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

Translated by ChatGPT 5