903C. Boxes Packing

greedy, 1200, https://codeforces.com/problemset/problem/903/C

Mishka has got n empty boxes. For every i (1 ≤ i ≤ n), i-th box is a cube with side length a~i~.

Mishka can put a box i into another box j if the following conditions are met:

i-th box is not put into another box;
j-th box doesn't contain any other boxes;
box i is smaller than box j (a~i~ < a~j~).

Mishka can put boxes into each other an arbitrary number of times. He wants to minimize the number of visible boxes. A box is called visible iff it is not put into some another box.

Help Mishka to determine the minimum possible number of visible boxes!

Input

The first line contains one integer n (1 ≤ n ≤ 5000) — the number of boxes Mishka has got.

The second line contains n integers $a_{1}, a_{2}, . . ., a_{n} (1 \leq a_{i} \leq 10^{9})$ , where $a_{i}$ is the side length of i-th box.

Output

Print the minimum possible number of visible boxes.

Examples

input

3
1 2 3

output

input

4
4 2 4 3

output

Note

In the first example it is possible to put box 1 into box 2, and 2 into 3.

In the second example Mishka can put box 2 into box 3, and box 4 into box 1.

python

from collections import *
input()
print(max(Counter(input().split()).values()))

python

# 出现次数最多的盒子数就是最后剩下的盒子数:
"""
考虑最多的重复出现的盒子出现了M次,那么收纳完的盒子数
必须至少为M;再考虑有M条流水线,从大到小罗列在线上面,
前面比出现频次最高的盒子要大的盒子不够铺开时就把频次
最高的盒子放到那里,依次排序,可知最多就要M个盒子完成
收纳,所以只需要统计最大频次即可
"""
n = input()
l = list(input().split())
t = {}
for a in l:
    if a in t.keys():
        t[a] += 1
    else:
        t[a] = 1
M = 0
for b in t.keys():
    if t[b] > M:
        M = t[b]
print(M)

903C. Boxes Packing ​

903C. Boxes Packing