Тренировка 04.04.2013

Соревнование завершилось 04.04.13 в 22:00

A. Держать строй

Ограничение по времени: 2 с.
Ограничение по памяти: 256 МБ

В воинской части города Шатров продолжаются занятия по строевой подготовке. На этот раз Андрей Юрьевич выполняет очередное задание своего начальника Павла Андреевича. Для выполнения этого задания, Андрею Юрьевичу необходимо среди всех n солдат, стоящих в одной шеренге, выбрать отряд из k высоких солдат для выполнения строительных работ.

В качестве первого шага, Андрей Юрьевич приказал каждому солдату посчитать свой показатель роста. Для этого каждый солдат, стоящий в шеренге, должен посмотреть сначала в одну сторону и посчитать количество солдат в этой части шеренги, которые строго ниже его, потом посмотреть в другую сторону, посчитать такое же количество, и тогда сумма этих двух чисел и будет его показателем роста.

На втором шаге, основываясь на этом показателе, Андрей Юрьевич должен выбрать отряд. Поскольку за долгие дни и ночи занятий строевой подготовкой солдаты успели хорошо познакомиться и даже подружиться со своими соседями в шеренге, Андрей Юрьевич решил выбрать в шеренге такой непрерывный подотрезок из ровно k солдат, у которого сумма показателей роставсех солдат максимальна.

Обладая информацией о росте каждого солдата в шеренге, помогите Андрей Юрьевичу найти оптимальный подотрезок.

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

Первая строка входных данных содержит два целых числа: n и k (1 ≤ k ≤ n ≤ 100000) — количество солдат в строю и необходимый размер отряда,  соответственно. Следующая строка содержит n целых чисел hi (1 ≤ hi ≤ 109) — рост i-го слева солдата в шеренге.

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

В выходные данные выведите одно целое число l — левый конец подотрезка из k солдат с максимальным показателем роста. Если таких отрезков несколько, выведите самый левый.

Пример

Стандартный вводСтандартный вывод
4 2
1 2 4 3
3
4 2
2 1 1 2
1