配点 : $600$ 点

問題文

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

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

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

制約

• 入力は全て整数
• $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)$ です。この入力には $6$ 個のクエリが含まれます。

$1$ 個目のクエリは $(l, r) = (6, 10)$ です。人 $6$ と人 $8$ 、人 $7$ と人 $10$ を組にすることで、同じ色の服を着たペアを $2$ 組作ることができます。

$2$ 個目のクエリは $(l, r) = (5, 8)$ です。人 $5$ と人 $7$ 、人 $6$ と人 $8$ を組にすることで、同じ色の服を着たペアを $2$ 組作ることができます。

$l=r$ であるようなクエリも与えられます。