← 返回题目列表

AtCoder · arc068_b

D. 食卡者

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

分数: 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