Matryoshka Dolls

Time limit1sMemory limit128 MB

Summary

Given doll heights, nest each doll inside a strictly taller doll, each holding at most one, to minimize the number of outermost dolls.

Level: Easy3 of 10
Topics: Greedy, Sorting, Two pointers
Solved: No attempts yet

Problem

Adam received a box full of Matryoshka dolls (a traditional Russian nesting doll) from his friend Matryona. Every doll has a hollow bottom, so one doll can hold exactly one smaller doll directly inside it.

All the dolls have the same shape but different sizes. Doll $i$ is described by a single number $h_i$ , its height. Doll $i$ fits directly inside doll $j$ if and only if $h_i < h_j$ , and each doll may contain at most one doll immediately inside it (that inner doll may in turn hold another doll, forming a nested stack).

Adam wants to nest the dolls so that the number of outermost dolls (dolls that are inside no other doll) is as small as possible. Given the heights of all the dolls, compute this minimum possible number of outermost dolls.

Input

The input consists of multiple test cases. Each test case begins with a line containing an integer $N$ ( $1 \le N \le 10^5$ ), the number of dolls. Each of the next $N$ lines contains one integer $h_i$ ( $1 \le h_i \le 10^9$ ), the height of the $i$ -th doll in centimeters. The input ends with a line containing $N = 0$ , which must not be processed.

Output

For each test case, print a single line containing the minimum possible number of outermost dolls after nesting the dolls optimally.

Examples3

Example 1

Input

Expected output

2
3
1

Example 2
Input
```
1
42
0
```
Expected output
```
1
```
Example 3
Input
```
5
7
7
7
7
7
0
```
Expected output
```
5
```