Хлоя недавно установила на свой телефон игру «Zuma». Игроку даётся ряд из n драгоценных камней, i-й из которых имеет цвет c
i. Цель игры — уничтожить все камни за как можно меньшее количество секунд.
За одну секунду Хлоя может выбрать любую подстроку (последовательность стоящих рядом камней), являющуюся палиндромом, и удалить её. После удаления данной подстроки оставшиеся камни сдвигаются, чтобы снова образовать непрерывный ряд. Какое минимальное количество секунд необходимо, чтобы уничтожить всю строку?
Напомним, что строка (или подстрока) является палиндромом, если она одинаково читается как слева направо, так и справа налево. В данном случае это означает, что цвет первого камня равен цвету последнего камня, цвет второго равен цвету предпоследнего и так далее.
Входные данные:
В первой строке входных данных записано единственное число n (1 ≤ n ≤ 500) — количество камней в изначальном ряду.
Во второй строке записано n целых чисел, i-е из которых равно c
i (1 ≤ c
i ≤ n) — цвет i-го камня в изначальном ряду.
Выходные данные:
Выведите единственное целое число — минимальное количество секунд, необходимое чтобы удалить все камни.
Примеры:
| Входные данные |
Выходные данные |
3
1 2 1 |
1 |
3
1 2 3 |
3 |
7
1 4 4 2 3 2 1 |
2 |
Пояснения:
Последовательность в третьем примере: [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []