当前没有测试数据。

G - 区间配对查询

分数：600分

问题描述

有$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$个查询的答案，以整数形式给出。 建议使用快速输入和输出方法，因为输入和输出可能很大。

---

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

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$。