Задача №113606. Маша и матрёшки
Маше на день рождения подарили набор матрёшек!
Теперь Маша сидит и вкладывает их одна в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки 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 ).
Выведите одно число — максимальное количество матрёшек, которые можно вложить друг в друга.
3 2 10 2
2
6 2 1 2 1 3 4
4
4 3 1 4 2
4