Non-decreasing Subarray Game

Problem Description

Yuto and Platina are about to play a non-decreasing-subarray game.

Specifically, given an array $A$ of length $N$, and bound indices $L$ and $R$.

Yuto first chooses a number in $[L, R]$ and shows it to Platina.

Then Platina also chooses a number in $[L, R]$.

Suppose Yuto chooses $a$ and Platina chooses $b$.

The score of this round is the number of non-decreasing subarrays of $A[\min(a,b):\max(a,b)]$ ($A[l:r]$ denotes the new array formed by the contiguous segment of $A$ from index $l$ to $r$).

Note: a subarray of array $B$ is obtained by deleting some (possibly empty) prefix and suffix of $B$.

Yuto wants the score to be as small as possible, while Platina wants it as large as possible.

They will play on the array $Q$ times. For each game, output the final score.

Input Format

The first line contains a positive integer $N$, the length of array $A$.

The next line contains $N$ positive integers, representing $A_1, A_2, \dots, A_N$.

The third line contains a positive integer $Q$, the number of games.

The next $Q$ lines each contain two positive integers $L$ and $R$.

For all data: $1 \le N, Q \le 5 \times 10^5$, $1 \le A_i \le 10^9$, and $1 \le L \le R \le N$.

Output Format

For each game, output one positive integer: the final score of the game.

Sample Input

8
7 10 3 1 9 5 5 2
5
1 5
2 2
5 8
1 8
3 5

Sample Output

4
1
4
7
3