题目描述

有 $N$ 个人按顺序编号为 $1,2,\\dots,N$。第 $i$ 个人穿着颜色 $A_i$。

回答以下格式的 $Q$ 个查询。

• 给定整数 $l$ 和 $r$。只考虑第 $l,l+1,\\dots,r$ 个人，最多可以形成多少对穿着相同颜色的人？

约束条件

• 输入中的所有值均为整数。
• $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$。

输入

从标准输入读入数据，输入格式如下：

$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

10
1 2 3 2 3 1 3 1 2 3
6
6 10
5 8
3 6
4 4
1 6
1 10

示例输出1

2
2
1
0
3
4

我们有 $A=(1,2,3,2,3,1,3,1,2,3)$。此输入包含六个查询。

第一个查询是 $(l, r) = (6, 10)$。通过配对第 $6, 8$ 个人，以及第 $7, 10$ 个人，我们可以形成两对穿着相同颜色的人。

第二个查询是 $(l, r) = (5, 8)$。通过配对第 $5, 7$ 个人，以及第 $6, 8$ 个人，我们可以形成两对穿着相同颜色的人。

可能会有 $l=r$ 的查询。