На 14 февраля Денис решил подарить валентинку Насте и не придумал ничего лучше чем нарисовать на двери длины \(k\) (\(k \ge 3\)) огромное красное сердечко. Настю такой подарок очень смутил, поэтому она решила сломать дверь, сбросив её на горы.
Горы описываются последовательностью высот \(a_1, a_2, \dots, a_n\) в порядке слева направо (\(k \le n\)). Гарантируется, что соседние высоты не равны друг другу (то есть \(a_i \ne a_{i+1}\) для всех \(i\) от \(1\) до \(n-1\)).
Пиками гор на отрезке \([l,r]\) (от \(l\) до \(r\)) называются такие индексы \(i\), что \(l < i < r\), \(a_{i - 1} < a_i\) и \(a_i > a_{i + 1}\). Стоит отметить, что граничные для отрезка индексы \(l\) и \(r\) пиками не являются. Например, если \(n=8\) и \(a=[3,1,4,1,5,9,2,6]\), то на отрезке \([1,8]\) всего два пика (с индексами \(3\) и \(6\)), а на отрезке \([3, 6]\) — пиков нет.
Чтобы сломать дверь, Настя сбрасывает ее на некоторый отрезок \([l,l+k-1]\) подряд идущих гор длины \(k\) (\(1 \le l \le n-k+1\)). Когда дверь касается пиков гор, она разламывается на две части, после этого эти части продолжат падать в разных половинах и также ломаться на части при касании пиков гор и так далее. Формально, количество частей, на которое разобьется дверь, будет равно \(p+1\), где \(p\) — количество пиков на отрезке \([l,l+k-1]\).
Настя хочет сломать ее на максимальное количество кусочков. Помогите ей выбрать такой отрезок гор \([l, l+k-1]\), что количество пиков на нём — максимально. Если существует несколько оптимальных отрезков, Настя желает найти такой, для которого значение \(l\) — минимально.
Формально, то вам нужно выбрать такой отрезок гор \([l, l+k-1]\), на котором количество пиков максимально. Среди всех таких отрезков, вам нужно найти отрезок, имеющий минимальное значение \(l\).
Примечание
В первом примере нужно выбрать отрезок гор со \(2\) по \(7\), на этом отрезке индексы \(3\) и \(6\) являются пиками, поэтому ответ равен \(3\) (всего \(2\) пика, значит дверь разломится на \(3\) части). Не трудно заметить, что отрезки гор \([1, 6]\) и \([3, 8]\) не подойдут, так как на них всего \(1\) пик (для первого отрезка индекс \(6\) не является пиком, а для второго отрезка индекс \(3\) не является пиком).
Во втором примере нужно выбрать отрезок гор со \(2\) по \(4\), на этом отрезке индекс \(3\) является пиком, поэтому ответ равен \(2\) (всего \(1\) пик, значит дверь разломится на \(2\) части).
В третьем примере нужно выбрать отрезок гор с \(1\) по \(4\), на этом отрезке индекс \(3\) является пиком, поэтому ответ равен \(2\) (всего \(1\) пик, значит дверь разломится на \(2\) части). Можно заметить, что на отрезках \([2, 5]\), \([4, 7]\) и \([5, 8]\) количество пиков также равно \(1\), но у этих отрезков левая граница больше, чем у отрезка \([1, 4]\), поэтому они не являются правильным ответом.