Держать строй - 3

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

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

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

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

Первая строка входного файла содержит два целых числа: $n$ и $k$ ($1 \le k \le n \le 100000$) --- количество солдат в строю и необходимый размер отряда, соответственно. Следующая строка содержит $n$ целых чисел $h\_i$ ($1 \le h\_i \le 10^9$) --- рост $i$-го слева солдата в шеренге.

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