问题描述

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