Маше на день рождения подарили набор матрёшек!
Теперь Маша сидит и вкладывает их одну в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры a
i и a
j соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда a
i < a
j . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.
Маше особенно нравится, если она может, вкладывая матрёшки друг в друга, добиться того, что все они оказываются внутри одной самой большой матрёшки. Но, к сожалению, это не всегда возможно. Поэтому Маша решила убрать часть матрёшек в шкаф, оставив такой набор, чтобы их все можно было вложить друг в друга. Помогите Маше понять, какое максимальное количество матрёшек может быть в таком наборе.
Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число a
i , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ a
i ≤ 10 000 ).
Выходные данные
Выведите одно число — максимальное количество матрёшек, которые можно вложить друг в друга.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
2 10 2 |
2 |
| 2 |
6
2 1 2 1 3 4 |
4 |
| 3 |
4
3 1 4 2 |
4 |