← 返回题目列表

AtCoder · abc295_c

E. 袜子

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

你有 N 袜子。的颜色 i-th 袜子是 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