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 翻译