/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 枚の靴下があります。i 枚目の靴下の色は A_i です。
あなたは以下の操作をできるだけ多い回数行いたいです。最大で何回行うことができますか？
- まだペアになっていない靴下の中から同じ色の靴下を 2 枚選んでペアにする。
制約
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
6 4 1 7 4 1 4
出力例 1
2
以下のようにして、2 回の操作を行うことができます。
- 色が 1 である靴下を 2 枚選んでペアにする。
- 色が 4 である靴下を 2 枚選んでペアにする。
このとき、色が 4 である靴下と 7 である靴下が 1 枚ずつ残るため、これ以上操作はできません。 また、どのように操作をしても 3 回以上操作を行うことはできないため、2 を出力します。
入力例 2
1 158260522
出力例 2
0
入力例 3
10 295 2 29 295 29 2 29 295 2 29
出力例 3
4
Score : 300 points
Problem Statement
You have N socks. The color of the i-th sock is A_i.
You want to perform the following operation as many times as possible. How many times can it be performed at most?
- Choose two same-colored socks that are not paired yet, and pair them.
Constraints
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print an integer representing the answer.
Sample Input 1
6 4 1 7 4 1 4
Sample Output 1
2
You can do the operation twice as follows.
- Choose two socks with the color 1 and pair them.
- Choose two socks with the color 4 and pair them.
Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.
Sample Input 2
1 158260522
Sample Output 2
0
Sample Input 3
10 295 2 29 295 29 2 29 295 2 29
Sample Output 3
4