На столе в один ряд лежат n цветных шаров. Цвет i-го шара задан числом c_i.

Ряд разрешается очищать по следующему правилу: за один ход можно удалить любой непрерывный фрагмент, состоящий из шаров одного цвета, если длина этого фрагмента не меньше 2. После удаления оставшиеся слева и справа части ряда сдвигаются и соединяются, поэтому могут появиться новые подходящие фрагменты.

Одиночный шар удалить нельзя.

Перед началом удаления разрешается добавить в ряд несколько новых шаров. Каждый добавленный шар можно поместить в любое место ряда и выбрать для него любой цвет.

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

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

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

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

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

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

Ограничения

• 1 <= n <= 300
• 1 <= c_i <= 10

Примеры

Пример 1

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

1
1

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

1

Пример 2

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

2
1 1

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

0