题目描述

给出长度为 $N$ 的数列 $A_i$，表示第 $i$ 个人衣服颜色为 $A_i$。有 $M$ 次询问 $[l,r]$ 区间最多能组成多少对衣服颜色相同的人。

输入格式

第一行输入一个整数 $n$

接下来一行输入 $n$ 个整数代表 $a_1,a_2,\cdots,a_n$

第三行输入要给整数 $q$

接下来 $q$ 行每行输入两个整数 $l,r$ 代表一组询问。

输出格式

输出一共输出 $q$ 行，每行一个整数

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

提示

• $1\ \le\ N\ \le\ 10^5$
• $1\ \le\ Q\ \le\ 10^6$
• $1\ \le\ A_i\ \le\ N$

Sample Explanation 1

我们有 $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$ 。