Coin Piles

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2796
64-bit integer IO format: %I64d      Java class name: Main

Description

We have some coins on the table. Each coin is characterized by its size. We want to arrange these coins into successive piles so that the following hold:

1. The size of the top coin in each pile is strictly greater than the size of all the other coins in the same pile.
2. The size of the top coin in each pile is strictly greater than the size of the top coin in the previous pile.
3. The number of coins in each pile is strictly greater than the number of coins in the previous pile.

You will be given the size of each coin. You are to calculate the maximal number of piles that we can organize according to the given rules. Each coin should be used in exactly one pile.

Input

There are multiple cases (no more than 100).

There is two lines for each case. The first line is a number n (1 <= n <= 50), indicating the number of coins. A line with n integers follows, giving the sizes of the coins.

Note that the maximal of the sizes will be unique, so it's always possible to form at least one pile.

Output

For each case, output the maximal number of piles that we can organize.

Sample Input

6
1 2 2 2 2 3
6
1 1 2 2 2 3
6
1 2 2 2 3 4

Sample Output

2
3
3

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .