Сейчас самое время планировать новые трекинговые маршруты. Опишем холмистую местность массивом из nn чисел. Высота i-го холма равна hi. Маршрут должен идти по k подряд идущим холмам (учитывая тот холм, с которого маршут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору - переходить с более низкого холма на более высокий. Помогите разработать маршрут по k подряд идущим холмам слева направо, на котором количество подъемов будет минимальным. В качестве ответа требуется вывести минимальное возможное количество подъемов на таком маршруте. Входные данные В первой строке даны натуральные числа n и k (2≤k≤n≤2⋅105) - общее количество холмов и количество холмов в маршруте, соответственно. Во второй строке даны n целых чисел hi (1≤hi≤105) - высоты холмов. Выходные данные Выведите ответ на задачу. Примечание В первом примере можно начать с первого, второго или третьего холма, во втором примере - с третьего холма. Примеры
500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач