Description

You are given a sequence $a$ of length $n$.

There are $m$ queries. Each query gives an interval $[l, r]$. For each query, compute $|\{(a_i, a_j) : l \le i < j \le r \wedge a_i > a_j\}|$.

$1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers. The $i$-th number $a_i$ is the value at position $i$ in the sequence. It is guaranteed that $1 \leq a_i \leq n$.

The third line contains a positive integer $m$.

Then follow $m$ lines. Each line contains two positive integers separated by two spaces, denoted $l, r$, representing one query. It is guaranteed that $1 \leq l \le r \leq n$.

Output Format

Output $m$ lines. The $i$-th line contains one integer, which is the answer to the $i$-th query.

5
2 1 3 2 1
4
2 4
1 5
3 5
2 2

1
3
3
0

Hint

[Sample Explanation]

For the first query, the set is $\{(3,2)\}$.

For the second and third queries, the set is $\{(2,1),(3,1),(3,2)\}$.

For the fourth query, the set is the empty set.

[Source]

From the 2021 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2021).

Resources such as editorial solutions can be found at https://github.com/yylidiw/thupc_0/tree/master.

Translated by ChatGPT 5