Farmer Ron в Colorado строит лыжный курорт для коров, но бюджет допускает один подъёмник. Монорельс соединит бетонную начальную опору с конечной через промежуточные, каждая высотой0 над землёй. Прямой стальной отрезок соединяет соседние опоры и должен всюду быть над землёй.

Экономный FR минимизирует опоры. Измерил $N$ одинаковых участков $(2 \le N \le 5,000)$ с целой высотой $H$ $(0 \le H \le 1,000,000,000)$. Безопасность требует соседнее расстояние не более $K$ единиц $(1 \le K \le N - 1)$. Сталь жёсткая и прямая.

Найдите минимум опор: сталь целиком выше или касается земли, соседнее горизонтальное расстояние не более $K$, опоры на первом и последнем участках.

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

• Строка $1$: два целых через пробел $N$, $K$.
• Строки $2..N+1$: строка $i+1$ задаёт целую высоту участка $i$.

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

• Строка $1$: целое, минимум башен при этих условиях.

Примеры

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

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

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

5

Примечание

5 опор в1, 5, 7, 9, 13. Сталь касается земли в4 местах:1–5, 5–7, 7–9, 12–13.

4 опоры в1, 5, 9, 13 дают сталь под землёй5–9. При1, 7, 13 сталь сверху, но7 и13 дальше4 по горизонтали. Меньше5 опор с соседними расстояниями не более4 невозможно.

Источник оригинала: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

Автор задачи: Adam Rosenfield, 2004