Задача 4: Марсоход Учёные рассматривают участок поверхности Марса, который можно представить в виде последовательности точек с высотами H1, H2, ..., HN. Высота между двумя соседними точками меняется равномерно.
Для исследований необходимо собрать информацию с любого отрезка участка поверхности, длина которого равна K. Для этого запланировано выбрать некоторую точку L, высадить туда марсоход и отправить его последовательно по точкам HL, HL+1, ..., HL+K.
Марсоход работает от аккумулятора. На перемещение на одну единицу вверх марсоход тратит одну единицу энергии. При перемещении на одну единицу вниз марсоход накапливает одну единицу энергии. На горизонтальное перемещение энергия не тратится. Изначально у марсохода достаточно энергии, чтобы изучить любой отрезок интересующего учёных участка, а максимальный возможный запас аккумулятора не ограничен.Учёные хотят, чтобы для дальнейших исследований у марсохода осталось как можно больше энергии. Поэтому среди всех возможных вариантов им нужно найти такое L, чтобы итоговый запас аккумулятора после исследований оказался максимально возможным. Если таких L несколько, для определённости берется минимальное из возможных.
учёным найти номер стартовой точки L
Входные данные
В первой строке входных данных содержится целое число N (2 ≤ N ≤ 250.000) — количество точек на интересующем учёных участке поверхности Марса.
Во второй строке содержится целое число K (1 ≤ K < N) — длина отрезка, который должен пройти марсоход.
В следующих N строках вводятся целые числа H1, H2, ..., HN (1 ≤ Hi ≤ 109) — высоты точек.Выходные данные
Выведите единственное целое число L — номер стартовой точки для марсохода.
1.Стейтмент в программировании — это то же самое, что и «предложение» в русском языке. Мы пишем предложения, чтобы выразить какую-то идею. В языке C++ мы пишем стейтменты, чтобы выполнить какое-то задание
2. Массив, запись, файл
3. следование, ветвление, повторение
4.Алгоритм — набор инструкций, четко описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Свойства алгоритмов: Дискретность,детерминированность,понятность,конечность,универсальность, результативность.
.
.
.
3.Следование — алгоритмическая конструкция, отображающая естественный, последовательный порядок действий. Алгоритмы, в которых используется только структура «следование», называются линейными алгоритмами.Ветвление — алгоритмическая конструкция, в которой в зависимости от результата проверки условия («да» или «нет») предусмотрен выбор одной из двух последовательностей действий (ветвей). Алгоритмы, в основе которых лежит структура «ветвление», называют разветвляющимися. Повторение — алгоритмическая конструкция, представляющая собой последовательность действий, выполняемых многократно. Алгоритмы, содержащие конструкцию повторения, называют циклическими или циклами. Последовательность действий, многократно повторяющаяся в процессе выполнения цикла, называется телом цикла.