Masha got a set of nesting dolls for her birthday!
Now Masha sits and puts them one into the other. She noticed that nesting dolls differ in size, and one fits inside the other only if its dimensions are strictly smaller. So, if there are two nested dolls i and j , and their sizes are a
i and a
j respectively, then nested doll i is nested inside nested doll j if and only if a
i < a
j . Of course, only one other nesting doll can be put directly inside the nesting doll, otherwise it will turn out sloppy, and Masha — very neat girl.
Masha especially likes it if she can put nesting dolls into each other so that they all end up inside one largest nesting doll. But, unfortunately, this is not always possible. Therefore, Masha decided to put some of the nesting dolls in the closet, leaving such a set so that they could all be put into each other. Help Masha understand the maximum number of nesting dolls in such a set.
Input
The first line contains the number n — the number of dolls given to Masha ( 1 ≤ n ≤ 1000 ). The next line contains n space-separated numbers — matryoshka sizes. The number a
i , standing in place of i , specifies the size of the doll with number i ( 1 ≤ a
i ≤ 10 000 ).
Imprint
Print one number — the maximum number of dolls that can be nested inside each other.
Examples
| # |
Input |
Output |
| 1 |
3
2 10 2
| 2 |
| 2 |
6
2 1 2 1 3 4
| 4 |
| 3 |
4
3 1 4 2
| 4 |