题目描述

すぬけくん决定玩一款纸牌游戏。有一叠由 $N$ 张卡牌组成的牌堆，从上往下第 $i$ 张卡牌上写有整数 $A_i$。

すぬけくん可以对这叠卡牌进行 $0$ 次或多次如下操作，使得剩下的卡牌上写的数字互不相同。请你求出最多能保留多少张卡牌。

操作：从牌堆中任意取出 $3$ 张卡牌。从这 $3$ 张卡牌中，选出写有最大值的卡牌 $1$ 张和写有最小值的卡牌 $1$ 张，将这两张卡牌吃掉。剩下的 $1$ 张卡牌放回牌堆。

保证 $N$ 是奇数，并且一定可以至少保留 $1$ 张卡牌。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $A_3$ ... $A_N$

输出格式

请输出答案。

样例 1

输入

5
1 2 1 3 7

输出

3

样例 2

输入

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

输出

7

说明/提示

限制条件

• $3 \leq N \leq 10^{5}$
• $N$ 是奇数
• $1 \leq A_i \leq 10^{5}$
• $A_i$ 是整数

样例解释 1

一种最优的操作方式是进行 $1$ 次操作，取出 $1,1,2$。吃掉最大值 $2$ 和最小值 $1$ 的卡牌各 $1$ 张，剩下的 $1$ 写的卡牌放回牌堆。此时牌堆中剩下 $1,3,7$，它们互不相同。

由 ChatGPT 4.1 翻译