【题目描述】

小灰灰有 $n$ 枚糖，其中第 $i$ 枚糖的类型为 $a_i$。

小灰灰注意到他的体重正在增长，所以前去拜访了一位医生。

医生建议小灰灰要少摄入糖分，只吃掉他所有糖的 $\dfrac{n}{2}$ 即可（$n$ 是一个偶数）。小灰灰非常喜欢这些糖，他想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 $n$ 的整数数组 $a$ ，输出小灰灰在仅吃掉 $\dfrac{n}{2}$ 枚糖的情况下，可以吃到糖的最多种类数。

【输入描述】

第一行一个整数代表 $n$

接下来一行 $n$ 个空格分隔的整数，第 $i$ 个整数代表 $a_i$

保证：

• $2\le n \le 10^5$，$n$ 是一个偶数

• $-10^5\le a_i \le 10^5$

【输出描述】

输出一行一个整数代表答案

【样例 1】

【样例 1 输入】

4
1 3 1 2

【样例 1 输出】

2

【样例 2】

【样例 2 输入】

6
1 1 2 2 3 3

【样例 2 输出】

3

【样例 3】

【样例 3 输入】

4
6 6 6 6

【样例 3 输出】

1