问题 G: 区间配对
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：9
解决：1
题目描述
有 $N$ 个人，编号 $1 \sim N$，第 $i$ 个人穿了 $A_i$ 颜色的衣服，有 $Q$ 次查询，每次查询给出一个范围 $[l, r]$ 问 $A_l \cdots A_r$ 之间最多有多少对配对成功，我们称有一对配对成功意味着两人穿的衣服颜色相同，注意每个人只能配对一次
输入
第一行一个整数 $1 \le N \le 10^5$ 代表人数
第二行 $N$ 个整数 $1 \le A_i \le N$ 代表每个人穿的衣服颜色
第三行一个整数 $1 \le Q \le 10^6$ 代表询问个数
接下来 $Q$ 行每行两个整数 $1 \le l \le r \le N$
第二行 $N$ 个整数 $1 \le A_i \le N$ 代表每个人穿的衣服颜色
第三行一个整数 $1 \le Q \le 10^6$ 代表询问个数
接下来 $Q$ 行每行两个整数 $1 \le l \le r \le N$
输出
每次询问输出一个整数表示最大配对对数并换行
样例输入 复制
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