P7601 [THUPC 2021] 区间本质不同逆序对

给定一个长为 $n$ 的序列 $a$。 有 $m$ 次询问，每次询问给定一个区间 $[l,r]$，求 $|\{(a_i,a_j) : l\le ia_j\}|$。 $1\le n\le 10^5$，$1\le m\le 5\times 10^5$。

第一行一个正整数 $n$。 第二行 $n$ 个正整数，其中第 $i$ 个数 $a_i$ 表示序列第 $i$ 个位置的值，保证 $1\leq a_i \leq n$。 第三行一个正整数 $m$。 之后 $m$ 行，每行用两个空格隔开的正整数，分别表示 $l,r$，表示一次询问，保证 $1\leq l\le r \leq n$。

输出 $m$ 行，第 $i$ 行输出一行一个整数，表示第 $i$ 次询问的答案。

**【样例解释】** 对于第一次询问，集合为 $\{(3,2)\}$。 对于第二次与第三次询问，集合为 $\{(2,1),(3,1),(3,2)\}$。 对于第四次询问，集合为空集。 **【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。 题解等资源可在 [https://github.com/yylidiw/thupc_0/tree/master](https://github.com/yylidiw/thupc_0/tree/master) 查看。