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

Дана перестановка $$$p$$$ длины $$$n$$$ и целое число $$$k$$$. Рассмотрим перестановку $$$q$$$ длины $$$n$$$ такую, что для любых целых чисел $$$i$$$ и $$$j$$$, где $$$1 \le i < j \le n$$$, выполняется $$$$$$p_{q_i} \le p_{q_j} + k.$$$$$$

Найдите минимально возможное количество инверсий, которое может быть в перестановке $$$q$$$.

Перестановкой является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Инверсия в перестановке $$$a$$$ — это пара индексов $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$), такая, что $$$i < j$$$, но $$$a_i > a_j$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 5000$$$, $$$1 \le k \le 8$$$).

Вторая строка содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

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

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

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

В первом примере единственный вариант перестановки $$$q = [1]$$$ ($$$0$$$ инверсий). Тогда $$$p_{q_1} = 1$$$.

Во втором примере единственный вариант с $$$1$$$ инверсией — $$$q = [1, 3, 2]$$$. Тогда $$$p_{q_1} = 2$$$, $$$p_{q_2} = 1$$$, $$$p_{q_3} = 3$$$.

В третьем примере один из возможных вариантов с $$$6$$$ инверсиями — $$$q = [3, 4, 5, 1, 2]$$$. Тогда $$$p_{q_1} = 3$$$, $$$p_{q_2} = 2$$$, $$$p_{q_3} = 1$$$, $$$p_{q_4} = 5$$$, $$$p_{q_5} = 4$$$.