Russian Dolls (Intuit India)

Put smaller dolls inside larger ones; dolls of the same size cannot nest inside each other. After nesting as much as possible, output the minimum number of dolls left.

输入格式

The input gives N (1≤N≤100000), then a line of N sizes (1..100000).

输出格式

Output the answer as described; for array answers, separate values with spaces.

样例 1

输入：

4
2 2 3 3

输出：

2

样例 2

输入：

6
1 2 2 3 4 5

输出：

2

样例 3

输入：

1
4

输出：

1

样例说明

Count the occurrences of each size; the answer is the maximum frequency.

Correctness: each size appears at most once in any nesting chain, so the most frequent size needs at least that many chains. Conversely, sort the sizes and assign them round-robin by index to that many chains; sizes within each chain strictly increase, so every doll fits into a chain.

Complexity: O(N) time, O(N) space.