Гра
Боян грає в комп'ютерну гру. Спочатку є 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).
Вихідні дані
Виведіть найбільшу кількість очок, яку може отримати Боян.