Вам задан массив \(a_1, a_2, \dots, a_n\). Вы можете выполнять на нем следующую операцию произвольное количество раз:
- Выбираем два равных соседних элемента \(a_i = a_{i + 1}\) (если такие существуют).
- Заменяем их на один элемент со значением \(a_i + 1\).
После каждой такой операции длина массива уменьшается на один (и элементы перенумеровываются соответствующим образом). Массив \(a\) какой минимальной длины вы можете получить?
Выходные данные
Выведите единственное число — минимально возможную длину массива, которую можно получить после применения операции, описанной выше, произвольное количество раз.
Примечание
В первом примере, одна из оптимальных последовательностей операций такая: \(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\).
В третьем и четвертом примере, не возможно применить операцию ни разу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 3 2 2 3
|
2
|
|
2
|
7
3 3 4 4 4 3 3
|
2
|
|
3
|
3
1 3 5
|
3
|
|
4
|
1
1000
|
1
|