102952: [Atcoder]ABC295 C - Socks

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

问题描述

你有$N$只袜子。第$i$只袜子的颜色为$A_i$。

你想尽可能多的执行以下操作。最多能执行多少次？

• 选择两只颜色相同的还未配对的袜子，将它们配对。

限制条件

• $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

你可以按照以下方式执行操作两次：

• 选择两只颜色为1的袜子并将它们配对。
• 选择两只颜色为4的袜子并将它们配对。

然后，你将剩下一只颜色为4的袜子和一只颜色为7的袜子，所以你不能再执行操作了。 没有方法可以执行三次或更多次操作，所以你应该打印2。

样例输入2

1
158260522

样例输出2

0

样例输入3

10
295 2 29 295 29 2 29 295 2 29

样例输出3

4