A10741 | Vladik and cards

Vladik was bored on his way home and decided to play the following game. He took $n$ cards and put them in a row in front of himself. Every card has a positive integer number not exceeding $8$ written on it. He decided to find the longest subsequence of cards which satisfies the following conditions:

- the number of occurrences of each number from $1$ to $8$ in the subsequence doesn't differ by more then $1$ from the number of occurrences of any other number. Formally, if there are $c_{k}$ cards with number $k$ on them in the subsequence, than for all pairs of integers  the condition $|c_{i}-c_{j}|<=1$ must hold.
- if there is at least one card with number $x$ on it in the subsequence, then all cards with number $x$ in this subsequence must form a continuous segment in it (but not necessarily a continuous segment in the original sequence). For example, the subsequence $[1,1,2,2]$ satisfies this condition while the subsequence $[1,2,2,1]$ doesn't. Note that $[1,1,2,2]$ doesn't satisfy the first condition.

Please help Vladik to find the length of the longest subsequence that satisfies both conditions.

The first line contains single integer $n$ ( $1<=n<=1000$ ) — the number of cards in Vladik's sequence.

The second line contains the sequence of $n$ positive integers not exceeding $8$ — the description of Vladik's sequence.

Print single integer — the length of the longest subsequence of Vladik's sequence that satisfies both conditions.