B. Zuma
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Генос недавно установил на свой телефон игру «Zuma». Игроку даётся ряд из n драгоценных камней, i-й из которых имеет цвет ci. Цель игры — уничтожить все камни за как можно меньшее количество секунд.

За одну секунду Генос может выбрать любую подстроку (последовательность стоящих рядом камней), являющуюся палиндромом, и удалить её. После удаления данной подстроки оставшиеся камни сдвигаются, чтобы снова образовать непрерывный ряд. Какое минимальное количество секунд необходимо, чтобы уничтожить всю строку?

Напомним, что строка (или подстрока) является палиндромом, если она одинаково читается как слева направо, так и справа налево. В данном случае это означает, что цвет первого камня равен цвету последнего камня, цвет второго равен цвету предпоследнего и так далее.

Входные данные

В первой строке входных данных записано единственное число n (1 ≤ n ≤ 500) — количество камней в изначальном ряду.

Во второй строке записано n целых чисел, i-е из которых равно ci (1 ≤ ci ≤ n) — цвет i-го камня в изначальном ряду.

Выходные данные

Выведите единственное целое число — минимальное количество секунд, необходимое чтобы удалить все камни.

Примеры
Входные данные
3
1 2 1
Выходные данные
1
Входные данные
3
1 2 3
Выходные данные
3
Входные данные
7
1 4 4 2 3 2 1
Выходные данные
2
Примечание

В первом примере Генос может уничтожить весь ряд за 1 секунду.

Во втором примере Генос может уничтожать только по одному камню в секунду за раз, поэтому на весь ряд у него уйдёт 3 секунды.

В третьем примере один из возможных способов достижения оптимального времени –– сперва уничтожить 4 4, а затем уничтожить 1 2 3 2 1.