P7601 [THUPC 2021] Distinct Inversion Pairs in an Interval

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

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 $m$ lines. The $i$-th line contains one integer, which is the answer to the $i$-th query.

**[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](https://github.com/yylidiw/thupc_0/tree/master). Translated by ChatGPT 5