Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Библиарий Тигурий обнаружил в архиве летопись, описывающую времена создания Империума человечества. Летописцы каждый день фиксировали текущее количество сторонников Императора, и (о ужас!) в некоторые дни это число не росло, а даже уменьшалось. "Наверняка, это ошибка" - определил Тигурий, и решил удалить часть записей таким образом, чтобы (согласно оставшимся) количество сторонников Императора от записи к записи только увеличивалось. Кроме того, чтобы подправленная летопись выглядела правдоподобной (просто менее подробной), интервал между последовательными записями (разность их порядковых номеров) должен составлять не менее `X` дней. Помогите библиарию достичь своей цели, удалив минимальное число записей.
В первой строке ввода содержатся 2 натуральных числа `N` (`1<=N<=10^5`, число записей) и `X` (`1<=X<=N`, минимальный интервал между записями).
В следующей строке вводятся `N` натуральных чисел не более `10^9` каждое - число сторонников в соответствующий день.
Выведите единственное натуральное число - минимальное число записей, которые нужно удалить, чтобы все условия были выполнены.
```sample Пример ввода
6 1
1 2 52 87 146 100500
```
```sample Пример вывода
0
```
```sample Пример ввода
8 2
1 2 3 10 1000 5 200 100
```
```sample Пример вывода
4
```
Пояснение: исправленная летопись может выглядеть как 1, _, 3, _, _, 5, _, 100 - соседние записи относятся к дням, отличающимся как минимум на 2, и все числа строго возрастают.
Начало
Рабочее место участника
Нахождение наидлиннейшей возрастающей подпоследовательности