← 返回题目列表

Codeforces · 903/C

C. 盒子包装

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

Mishka 有 n 个空盒子。对于每个 i (1 ≤ i ≤ n),第 i 个盒子是边长为 ai 的立方体。

如果满足以下条件,Mishka 可以将一个盒子 i 放入另一个盒子 j 中:

- 第 i 个盒子没有放入另一个盒子中;
- 第 j 个盒子不包含任何其他盒子;
- 框 i 小于框 j (ai < aj)。

Mishka 可以将盒子相互放入任意次数。他想尽量减少可见盒子的数量。一个盒子被称为可见,当且仅当它没有被放入另一个盒子中。

帮助 Mishka 确定可见框的最小可能数量!

输入

第一行包含一个整数 n (1 ≤ n ≤ 5000) — Mishka 拥有的盒子数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109),其中 ai 是第 i 个盒子的边长。

输出

打印尽可能少的可见框数。

示例

输入 #1

3
1 2 3

输出 #1

1

输入 #2

4
4 2 4 3

输出 #2

2

注意

在第一个示例中,可以将框 1 放入框 2,将 2 放入框 3。

在第二个示例中,Mishka 可以将盒子 2 放入盒子 3,将盒子 4 放入盒子 1。