Перед вами лежит ряд из n цветных плиток. Цвет i-й плитки задаётся числом c_i.

За один ход можно очистить любую непрерывную группу плиток, если последовательность их цветов является палиндромом, то есть читается одинаково слева направо и справа налево. В частности, одна плитка всегда подходит, а также подходят две соседние плитки одного цвета.

После удаления выбранной группы оставшиеся плитки сдвигаются, и ряд снова становится непрерывным.

Требуется определить минимальное количество ходов, за которое можно полностью очистить весь ряд плиток.

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

Первая строка содержит одно целое число n — количество плиток.

Вторая строка содержит n целых чисел c_i — цвета плиток в ряду.

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

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

Ограничения

• 1 <= n <= 500
• 1 <= c_i <= 20

Примеры

Пример 1

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

1
1

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

1

Пример 2

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

5
1 2 3 4 5

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

5