Problem Description

Given a sequence $a$ of length $n$.

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

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, where the $i$-th integer $a_i$ denotes the value at position $i$ of the sequence.

The third line contains an integer $m$.

Then follow $m$ lines, each line contains two integers separated by two spaces, denoting $l,r$, which represent a query. It is guaranteed that $l\le r$.

Output Format

Output $m$ lines. The $i$-th line contains one integer, representing 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

Idea: nzhtl1477, Solution: nzhtl1477&ccz181078, Code: ccz181078, Data: w33z8kqrqk8zzzx33&nzhtl1477.

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 an empty set.

For $100\%$ of the testdata, the Constraints are $1\le n\le 10^5$, $1\le m\le 5\times 10^5$, $1\le a_i\le n$.

Translated by ChatGPT 5