Задача №114301. Маршрут для трекинга
Сейчас самое время планировать новые трекинговые маршруты.
Опишем холмистую местность массивом из \(n\) чисел. Высота \(i\)-го холма равна \(h_i\). Маршрут должен идти по \(k\) подряд идущим холмам (учитывая тот холм, с которого маршут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору - переходить с более низкого холма на более высокий.
Помогите разработать маршрут по \(k\) подряд идущим холмам слева направо, на котором количество подъемов будет минимальным. В качестве ответа требуется вывести минимальное возможное количество подъемов на таком маршруте.
В первой строке даны натуральные числа \(n\) и \(k\) (\(2 \le k \le n \le 2\cdot 10^5\)) - общее количество холмов и количество холмов в маршруте, соответственно.
Во второй строке даны \(n\) целых чисел \(h_i\) (\(1 \le h_i \le 10^5\)) - высоты холмов.
Напоминаем, что два числа из одной строки в языке Python можно считать так: n, m = map(int, input().split())
Выведите ответ на задачу.
В первом примере можно начать с первого, второго или третьего холма, во втором примере - с третьего холма.
5 3 2 1 2 2 4
1
7 4 1 2 3 3 3 1 2
0