/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 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 個目のクエリに対する答えを整数として出力せよ。
なお、入出力が大きくなる場合があるので、高速な方法で入出力を行うことを推奨する。
入力例 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 であるようなクエリも与えられます。
Score : 600 points
Problem Statement
N people numbered 1,2,\dots,N are standing in a row. Person i wears Color A_i.
Answer Q queries of the format below.
- You are given integers l and r. Considering only Person l,l+1,\dots,r, how many pairs of people wearing the same color can be formed at most?
Constraints
- All values in input are integers.
- 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 in each query.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_N
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q
Here, \mathrm{Query}_i represents the i-th query.
Each query is in the following format:
l r
Output
Print Q lines. The i-th line should contain the answer for the i-th query as an integer. The use of fast input and output methods is recommended because of potentially large input and output.
Sample Input 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
Sample Output 1
2 2 1 0 3 4
We have A=(1,2,3,2,3,1,3,1,2,3). This input contains six queries.
The first query is (l, r) = (6, 10). By pairing Person 6, 8 and paring Person 7, 10, we can form two pairs of people wearing the same color.
The second query is (l, r) = (5, 8). By pairing Person 5, 7 and paring Person 6, 8, we can form two pairs of people wearing the same color.
There can be a query where l=r.