Игра
Боян играет в компьютерную игру. Изначально имеется n шаров, расположенных в ряд. На каждом шаре написано число, любые два последовательных шара имеют разные числа. Игра состоит из следующих шагов:
Игрок удаляет шар из ряда.
Пока последовательные шары имеют одинаковые числа, они автоматически удаляются из ряда.
Если ряд еще содержит шары, переходим на шаг 1, иначе игра заканчивается.
Очки считаются как количество шаров, которые автоматически удаляются. Цель игры - максимизировать количество очков.
Боян удаляет шар номер 3. Остаются шары {1, 2, 2, 1, 5}.
Удаляя последовательные шары с равными номерами, мы получим {1, 2, 2, 1, 5} -> {1, 1, 5} -> {5}. Остается шар {5}.
Так как в ряду еще имеются шары, переходим на шаг 1.
Следующая итерация:
Боян удаляет шар номер 5. Остаются шары {}.
Последовательных шаров с равными числами больше нет.
Поскольку шаров в ряду не осталось, заканчиваем игру.
Количество шаров, удаленных автоматически, равно 4. Это наибольший возможный счет в этой игре. Боян много играет, но он все еще не уверен, играет ли он оптимально. Напишите программу, которая поможет ему найти лучший достижимый результат.
Входные данные
Первая строка содержит натуральное число n (1 ≤ n ≤ 500). Вторая строка содержит n натуральных чисел - числа, записанные на шарах (число на шаре ≤ 10^6).
Выходные данные
Выведите наибольшее количество очков, которое может получить Боян.