eolymp
bolt
Try our new interface for solving problems
Məsələlər

Matryoshka Dolls

Matryoshka Dolls

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Adam just got a box full of Matryoshka dolls (Russian traditional) from his friend Matryona. When he opened the box, tons of dolls poured out of the box with a memo from her:

Hi Adam, I hope you enjoy these dolls. But sorry, I didn't have enough time to sort them out. You'll notice that each doll has a hollow hole at the bottom which allows it to contain a smaller doll inside.

...

Yours,

Matryona

Adam, who already has so many things in his showcase already, decides to assemble the dolls to reduce the number of outermost dolls. The dolls that Matryona sent have the same shape but di erent sizes. That is, doll i can be represented by a single number h_i denoting its height. Doll i can fit inside another doll j if and only if h_i < h_j. Also, the dolls are designed such that each doll may contain at most one doll right inside it. While Adam is stacking his gigantic collection of Matryoshka dolls, can you write a program to compute the minimum number of outermost dolls so that he can figure out how much space he needs in his show case?

Giriş verilənləri

The input consists of multiple test cases. Each test case begins with a line with an integer N, 1N10^5, denoting the number of Matryoshka dolls. This is followed by N lines, each with a single integer h_i, 1h_i10^9, denoting the height of the i^th doll in cm. Input is followed by a single line with N = 0, which should not be processed.

Çıxış verilənləri

For each test case, print out a single line that contains an integer representing the minimum number of outermost dolls that can be obtained by optimally stacking the given dolls.

Nümunə

Giriş verilənləri #1
4
5
7
7
3
3
10
10
10
3
10
999999999
100000000
0
Çıxış verilənləri #1
2
3
1