P7448 [Ynoi2007] rdiq

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 ia_j\}|$.

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

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