题目描述

$1,2,\dots,N$ と番号付けられた人が並んでおり、人 $i$ は色 $A_i$ の服を着ています。

以下の形式で表される $Q$ 個のクエリに答えてください。

• 整数 $l,r$ が与えられる。 人 $l,l+1,\dots,r$ だけに着目したとき、同じ色の服を着た $2$ 人からなるペアは最大何組作れるか答えよ。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ 個目のクエリに対する答えを整数として出力せよ。
なお、入出力が大きくなる場合があるので、高速な方法で入出力を行うことを推奨する。

题目大意

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

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$
• 各クエリについて、 $1\ \le\ l\ \le\ r\ \le\ N$

Sample Explanation 1

$A=(1,2,3,2,3,1,3,1,2,3)$ です。この入力には $6$ 個のクエリが含まれます。 $1$ 個目のクエリは $(l,\ r)\ =\ (6,\ 10)$ です。人 $6$ と人 $8$ 、人 $7$ と人 $10$ を組にすることで、同じ色の服を着たペアを $2$ 組作ることができます。 $2$ 個目のクエリは $(l,\ r)\ =\ (5,\ 8)$ です。人 $5$ と人 $7$ 、人 $6$ と人 $8$ を組にすることで、同じ色の服を着たペアを $2$ 組作ることができます。 $l=r$ であるようなクエリも与えられます。