410781: GYM104103 B Matryoshka Inc

A prominent toy company Matryoshka Inc is going to launch a marketing campaign. They will invite participants to solve the following problem: there are $$$n$$$ matryoshkas in a row, numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th matryoshka's size is $$$s_i$$$. The participant's goal is to assemble a stack of matryoshkas using as many matryoshkas as possible. But, there is a restriction: they must create the stack using matryoshkas in order from left to right, from the smallest to largest (possibly, skipping some of them).

To begin, you can choose the first matryoshka, then select some other matryoshka with a larger index and strictly larger size, and then put the first matryoshka inside the second one. After this, you can select another matryoshka whose size and index are strictly larger than the size and index of previously selected matryoshkas, put the first two matryoshkas inside the third one, and so on. When you are done, your score is the number of matryoshkas used. In the case when you cannot put a matryoshka inside another one with a larger index, or if there is just one matryoshka, the score is considered to be equal to one.

Now the CEO of Matryoshka Inc is interested in the maximum score a participant can achieve. They sent you a message with $$$n$$$ numbers $$$s_1, \ldots, s_n$$$, but there were some connection issues. Instead of $$$n$$$ numbers $$$s_1, \ldots, s_n$$$, you received $$$n$$$ numbers $$$a_1, \ldots, a_n$$$, where $$$a_i$$$ is equal to $$$s_i$$$, but the digits were shuffled, possibly with leading zeroes.

There is very little time, so the CEO asks you to determine the maximum score a participant can achieve based only on $$$a_1, \ldots, a_n$$$. Recall that $$$a_i$$$ is a digit permutation of $$$s_i$$$, possibly with leading zeroes.

The first line contains the single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of matryoshkas.

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i < 10^{18}$$$). Each integer $$$a_i$$$ has at most $$$18$$$ digits, possibly, with leading zeroes.

Output a single integer — the maximum possible score that a participant can theoretically achieve.

Let's define $$$L$$$ as the maximum length of an input number $$$a_i$$$.

2
1 1

1

5
10 2 30 4 50

5

6
77 88 91 22 33 44

4

3
390100 200200 012

3

Let's consider the first example. In that case, you have only two matryoshkas of equal sizes. It means that you can not put any matryoshka inside the other one. So, the answer for the first example is $$$1$$$.

Lets's consider the second example. Theoretically, the sequence of the matryoshka's sizes could be $$$01$$$, $$$2$$$, $$$03$$$, $$$4$$$, $$$05$$$. In that case, a participant could achieve a score equal to $$$5$$$. So, the answer for the second example is $$$5$$$.

Let's consider the third example. There are only two ways the real sequence of matryoshka's sizes could look like. The first one is $$$77$$$, $$$88$$$, $$$91$$$, $$$22$$$, $$$33$$$. And the second one is $$$77$$$, $$$88$$$, $$$19$$$, $$$22$$$, $$$33$$$. It's easy to see that in the first case, the maximum score that the participant can achieve equals $$$3$$$, but in the second case, the maximum score that the participant can achieve equals $$$4$$$. So, the answer for the third example is $$$4$$$.

Let's consider the fourth example. There is a scenario where the sequence of the matryoshka's sizes is $$$000139$$$, $$$000202$$$, $$$210$$$. So, participant could assemble a stack of three matryoshkas. So, the answer for the forth example is $$$3$$$.