Владик заскучал по дороге домой и решил сыграть в следующую игру. Он взял n карт и положил их в ряд перед собой. На каждой карте Владика написано целое положительное число, не превосходящее 8. Он решил найти самую длинную подпоследовательность карт, для которой выполняются следующие условия:

• количество вхождений каждого числа от 1 до 8 в подпоследовательности отличается не более, чем на 1 от количества вхождений любого другого числа. Более формально, если в подпоследовательности c_k карт с числом k на них, то для всех выполняется |c_i - c_j| ≤ 1.
• если в подпоследовательности имеется карта с числом x, то все карты с числом x должны составлять непрерывный отрезок в этой подпоследовательности (но не обязательно быть непрерывным отрезком в исходной последовательности). Например, последовательность карт [1, 1, 2, 2] удовлетворяет данному условию, а [1, 2, 2, 1] — нет. Обратите внимание, что [1, 1, 2, 2] не удовлетворяет первому условию.

Помогите Владику и найдите максимальную длину подходящей подпоследовательности.