AT_abc242_g [ABC242G] Range Pairing Query

有 $1,2,\dots,N$ 号的人排成一排，第 $i$ 号人穿着颜色为 $A_i$ 的衣服。 请你回答 $Q$ 个如下形式的查询： - 给定整数 $l,r$。只考虑第 $l,l+1,\dots,r$ 号人，最多可以组成多少对穿着相同颜色衣服的两人组？

输入按以下格式从标准输入给出。 > $N$ $A_1$ $A_2$ $\dots$ $A_N$ $Q$ $\mathrm{Query}_1$ $\mathrm{Query}_2$ $\vdots$ $\mathrm{Query}_Q$ 其中，$\mathrm{Query}_i$ 表示第 $i$ 个查询。 每个查询的格式如下： > $l$ $r$

输出共 $Q$ 行。 第 $i$ 行输出第 $i$ 个查询的答案，答案为一个整数。 由于输入输出数据量较大，建议使用高效的输入输出方法。

### 数据范围 - 所有输入均为整数。 - $1\le N\le 10^5$ - $1\le Q\le 10^6$ - $1\le A_i\le N$ - 对于每个查询，$1\le l\le r\le N$ ### 样例解释 1 $A=(1,2,3,2,3,1,3,1,2,3)$。该输入包含 $6$ 个查询。第 $1$ 个查询为 $(l,r)=(6,10)$。可以将第 $6$ 号人与第 $8$ 号人配对，第 $7$ 号人与第 $10$ 号人配对，这样可以组成 $2$ 对穿着相同颜色衣服的两人组。第 $2$ 个查询为 $(l,r)=(5,8)$。可以将第 $5$ 号人与第 $7$ 号人配对，第 $6$ 号人与第 $8$ 号人配对，这样也可以组成 $2$ 对穿着相同颜色衣服的两人组。也可能会有 $l=r$ 的查询。 由 ChatGPT 4.1 翻译