← 返回题目列表

Codeforces · 1077/E

E. 专题竞赛

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

Polycarp 准备了 $$$n$$$ 竞争性编程问题。第 $$$i$$$ 问题的主题是 $$$a_i$$$,有些问题的主题可能会重合。

坡旅甲必须举办几场专题竞赛。每场比赛中的所有问题都应该有相同的主题,并且所有比赛都应该有成对不同的主题。他可能不会使用所有的问题。某些主题可能没有竞赛。

Polycarp 希望连续几天举办比赛,每天一场比赛。波利卡普希望以这样的方式举办一系列比赛:

- 每场比赛的问题数量恰好是上一场比赛(一天前)的两倍,第一场比赛可以包含任意数量的问题;
- 所有比赛中的问题总数应最大化。

你的任务是计算一组主题竞赛中的最大问题数。请注意,您不应该最大化比赛数量。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — Polycarp 准备的问题数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 问题的主题。

输出

打印一个整数——一组主题竞赛中的最大问题数。

示例

输入 #1

18
2 1 2 10 2 10 10 2 2 1 10 10 10 10 1 1 10 10

输出 #1

14

输入 #2

10
6 6 6 3 6 1000000000 3 3 6 6

输出 #2

9

输入 #3

3
1337 1337 1337

输出 #3

3

注意

在第一个示例中,最佳竞赛顺序是:$$$2$$$ 主题的问题 $$$1$$$、$$$4$$$ 主题的问题 $$$2$$$、$$$8$$$ 主题的问题 $$$10$$$。

在第二个示例中,最佳竞赛顺序是:$$$3$$$ 主题 $$$3$$$ 问题,$$$6$$$ 主题 $$$6$$$ 问题。

在第三个示例中,您可以获取主题 $$$1337$$$ 的所有问题(此类问题的数量为 $$$3$$$,因此答案为 $$$3$$$)并举办一场竞赛。