分数: 400 点
问题陈述
Snuke 决定玩一个使用纸牌的游戏。 他的牌组包括 N 卡。上 i从顶部算起的第一张牌,一个整数 写入 A_i 。
他将执行下面描述的操作零次或多次,以便写在其余卡片上的值将两两不同。找出剩余卡牌的最大可能数量。在这里, N 为奇数,保证至少可以保留一张牌。
操作:从牌组中取出任意三张牌。在这三张牌中,吃两张:一张值最大,另一张值最小。然后,将剩余的一张卡放回牌库。
约束
- 3 ≦ N ≦ 10^{5}
- N 是奇数。
- 1 ≦ A_i ≦ 10^{5}
- A_i 是一个整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 A_3 ... A_{N}
输出
打印答案。
示例输入 1
5 1 2 1 3 7
示例输出 1
3
一种最佳解决方案是执行一次操作,取出两张卡 1 和一张带有 2。一张卡带有 1 和另一个 2 将被吃掉,剩余的卡牌带有 1 将返回甲板。然后,写在这副牌中剩余卡片上的值将两两不同: 1, 3 和 7.
示例输入 2
15 1 3 5 2 1 3 2 8 8 6 2 6 11 1 1
示例输出 2
7