Максимальный возможный выигрыш, который теоретически может получить участник

Популярная компания Matryoshka Inc, производящая игрушки, планирует запустить акцию, в
ходе которой всем желающим будет предложено решить следующую задачу: в ряд расставлены n
матрешек, пронумерованные от 1 до n; i-я из них имеет размер si
, причем si может иметь лидирующие нули. Участникам предлагается собрать цепочку из как можно большего числа вложенных
матрешек. Однако, есть ограничение, что собирать матрешки можно только в порядке слева направо, от меньшей к большей (матрешки можно пропускать, не обязательно использовать все подряд).
Более подробно: участник может взять любую матрешку, затем выбрать другую матрешку строго большего размера и расположенную правее данной, и положить первую внутрь второй. После
чего можно снова выбрать матрешку строго большего размера и расположенную правее последней
выбранной и положить первые две матрешки (где одна уже находится внутри другой) внутрь третьей. Такой процесс можно повторять сколько угодно раз. Выигрыш участника равен количеству
матрешек, которые он использовал в своих действиях, включая последнюю матрешку. В случае,
когда никакую матрешку нельзя положить внутрь более правой с большим размером, либо если в
ряду стоит всего одна матрешка, то выигрыш участника считается равным единице.
Директора компании заинтересовало, какой максимальный выигрыш сможет получить участник.
Чтобы это выяснить, он отправил вам числа s1, . . . , sn по специальному секретному каналу связи
компании Matryoshka Inc. Однако в ходе передачи сообщения произошел сбой, и цифры в числах
s1, . . . , sn перемешались. В итоге вы получили набор чисел a1, . . . , an, где ai — число, полученное из
si некоторой перестановкой цифр.
Поскольку до запуска акции осталось всего ничего, времени на повторную отправку нет. Поэтому директор попросил вас найти максимальный возможный выигрыш участника по известным
значениям a1, . . . , an. Учитывайте, что в теории настоящий размер i-й матрешки может быть равен
любой перестановке цифр ai
, в том числе содержащей ведущие нули.
Формат входных данных
Первая строка содержит одно число n (1 6 n 6 1000) — количество матрешек, участвующих в
акции.
Вторая строка содержит n целых чисел a1, a2, . . . , an (0 6 ai < 1018) — числа, полученные вами
по секретному каналу связи. Длина каждого числа, включая ведущие нули, не превосходит 18 цифр.
Формат выходных данных
Выведите единственное число — максимальный возможный выигрыш, который теоретически
может получить участник.
Система оценки
Обозначим за L максимальную длину входного числа ai.

Примеры:

стандартный ввод
2
1 1

стандартный вывод
1

стандартный ввод
5
10 2 30 4 50

стандартный вывод
5

стандартный ввод
6
77 88 91 22 33 44

стандартный вывод
4

стандартный ввод
3
390100 200200 012

стандартный вывод
3

Замечание
Рассмотрим первый пример. В акции участвует всего две матрешки с одинаковым размером,
равным единице. Поскольку матрешки одинаковых размеров не могут быть вложены друг в друга,
длина максимальной цепочки из вложенных матрешек равна 1.
Рассмотрим второй пример. Если предпололжить, что настоящие размеры матрешек равны 01, 2,
03, 4, 05, то участник может собрать цепочку из пяти матрешек. Поэтому ответ на второй пример —
5.
Рассмотрим третий пример. В этом случае существует всего два варинта настоящей последовательности размеров матрешек, которую вам отправляли по секретному каналу. Первая из них: 77,
88, 91, 22, 33, 44. Вторая: 77, 88, 19, 22, 33, 44. Как несложно видеть, в первом случае длина максимальной цепочки из матрешек равна 3, а во втором случае — 4. Поэтому ответ на третий пример
— 4.
Рассмотрим четвертый пример. Если предположить, что настоящие размеры матрешек равны
000139, 000202, 210, то участник может собрать цепочку из трех матрешек, сначала вложив первую
матрешку внутрь второй, а затем вложив первые две матрешки внутрь третьей. Таким образом,
ответ на четвертый пример — 3.

0