E. Сжатие массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a_1, a_2, \dots, a_n$$$. Вы можете выполнять на нем следующую операцию произвольное количество раз:

  • Выбираем два равных соседних элемента $$$a_i = a_{i + 1}$$$ (если такие существуют).
  • Заменяем их на один элемент со значением $$$a_i + 1$$$.

После каждой такой операции длина массива уменьшается на один (и элементы перенумеровываются соответствующим образом). Массив $$$a$$$ какой минимальной длины вы можете получить?

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

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 500$$$) — первоначальная длина массива $$$a$$$.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — первоначальный массив $$$a$$$.

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

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

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

В первом примере, одна из оптимальных последовательностей операций такая: $$$4$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$\rightarrow$$$ $$$5$$$ $$$3$$$.

Во втором примере, одна из оптимальных последовательностей операций такая: $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$5$$$ $$$4$$$ $$$\rightarrow$$$ $$$6$$$ $$$4$$$.

В третьем и четвертом примере, не возможно применить операцию ни разу.