問題文

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

入力例 1

10
1 2 3 2 3 1 3 1 2 3
6
6 10
5 8
3 6
4 4
1 6
1 10

出力例 1

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$ であるようなクエリも与えられます。