区间配对查询

题目描述

编号为 $1,2,\dots,N$ 的 $N$ 个人站成一排。第 $i$ 个人穿着颜色为 $A_i$ 的衣服。

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

给定整数 $l$ 和 $r$。只考虑第 $l,l+1,\dots,r$ 个人时,最多可以配成多少对穿相同颜色衣服的人?

输入格式

输入按以下格式从标准输入给出:

N
A_1 A_2 … A_N
Q
Query_1
Query_2
⋮
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$ 的查询。

数据范围

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

提示

由于输入和输出可能很大,推荐使用高速的输入输出方法。