AT_abc242_g [ABC242G] Range Pairing Query

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

### 制約 - 入力は全て整数 - $ 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 $ であるようなクエリも与えられます。