C. Palindromization
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

В этот раз Влад получил массив $$$a$$$ из $$$n$$$ целых чисел. За одну операцию Влад может выбрать любой отрезок этого массива и прибавить ко всем элементам на этом отрезке одинаковое число $$$x$$$ от $$$1$$$ до $$$k$$$ включительно.

Несмотря на то, что Влад привык работать с палиндромами, в этот раз у него возникли проблемы с тем, чтобы получить из $$$a$$$ палиндром за минимальное число действий. Помогите ему поскорее справиться с этой задачей.

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

Первая строка ввода содержит два целых числа $$$n$$$ и $$$k$$$ — размер исходного массива и ограничение на прибавляемые значения ($$$1 \le n \le 10^6$$$; $$$1 \le k \le 3$$$).

Во второй строке ввода через пробел даны $$$n$$$ целых чисел $$$a_i$$$ — элементы массива ($$$1 \le a_i \le 10^9$$$).

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

Выведите единственное число — минимальное количество операций, необходимое, чтобы сделать из массива $$$a$$$ палиндром.

Система оценки

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

ПодзадачаБаллыОграничения Необходимые подзадачи
0–примеры из условия
110$$$n, a_i \le 10$$$0
211$$$a_i \le 2$$$, $$$k=1$$$
312$$$a_i \le a_{i+1}$$$ для всех $$$i$$$
420$$$k = 1$$$2
522$$$k \le 2$$$4
625$$$k \le 3$$$, $$$n \le 1000$$$0, 1

Обратите внимание, что нет группы с $$$k = 3$$$ без каких-либо других дополнительных ограничений!

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

В первом примере нужно прибавить $$$1$$$ к отрезку $$$[1, 3]$$$, прибавить $$$1$$$ к отрезку [$$$1, 2$$$], а затем два раза прибавить $$$1$$$ к первому элементу. Таким образом после четырех операций массив равен $$$[5, 4, 4, 4, 5]$$$.

Во втором примере нужно прибавить $$$2$$$ к отрезку $$$[1, 1]$$$, прибавить $$$2$$$ к отрезку $$$[4, 5]$$$ и прибавить $$$1$$$ к отрезку $$$[4, 5]$$$, после чего прибавить $$$1$$$ к отрезку $$$[5, 5]$$$. Таким образом после четырех операций массив равен $$$[5, 6, 4, 4, 6, 5]$$$.

В третьем примере нужно прибавить $$$1$$$ к отрезку $$$[1, 4]$$$, прибавить $$$3$$$ к отрезку $$$[6, 7]$$$ и прибавить $$$1$$$ к отрезку $$$[7, 7]$$$. Таким образом после трех операций массив равен $$$[2, 5, 4, 2, 2, 4, 5, 2]$$$.