eolymp
bolt
Try our new interface for solving problems

Игра

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

  1. Игрок удаляет шар из ряда.

  2. Пока последовательные шары имеют одинаковые числа, они автоматически удаляются из ряда.

  3. Если ряд еще содержит шары, переходим на шаг 1, иначе игра заканчивается.

Очки считаются как количество шаров, которые автоматически удаляются. Цель игры - максимизировать количество очков.

  1. Боян удаляет шар номер 3. Остаются шары {1, 2, 2, 1, 5}.

  2. Удаляя последовательные шары с равными номерами, мы получим {1, 2, 2, 1, 5} -> {1, 1, 5} -> {5}. Остается шар {5}.

  3. Так как в ряду еще имеются шары, переходим на шаг 1.

Следующая итерация:

  1. Боян удаляет шар номер 5. Остаются шары {}.

  2. Последовательных шаров с равными числами больше нет.

  3. Поскольку шаров в ряду не осталось, заканчиваем игру.

Количество шаров, удаленных автоматически, равно 4. Это наибольший возможный счет в этой игре. Боян много играет, но он все еще не уверен, играет ли он оптимально. Напишите программу, которая поможет ему найти лучший достижимый результат.

Giriş verilənləri

Первая строка содержит натуральное число n (1n500). Вторая строка содержит n натуральных чисел - числа, записанные на шарах (число на шаре ≤ 10^6).

Çıxış verilənləri

Выведите наибольшее количество очков, которое может получить Боян.

Nümunə

Giriş verilənləri #1
6
1 2 3 2 1 5
Çıxış verilənləri #1
4
Giriş verilənləri #2
9
1 5 1 3 2 4 2 3 1
Çıxış verilənləri #2
6
Mənbə 2017 IX International autumn tournament in informatics, Shumen, Junior, Problem B