B. Настя и дверь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На 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$$$.

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

В первой строке записано целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных в тесте. Далее содержатся сами описания наборов.

В первой строке набора находятся два целых числа $$$n$$$ и $$$k$$$ ($$$3 \leq k \leq n \leq 2 \cdot 10^5$$$)  — количество гор и длина Настиной двери.

Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10 ^ 9$$$, $$$a_i \neq a_{i + 1}$$$), задающие высоты гор.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите два целых числа $$$t$$$ и $$$l$$$  — максимальное количество частей, на которое может разбиться дверь, и левую границу отрезка длины $$$k$$$, на который надо сбросить дверь.

Пример
Входные данные
5
8 6
1 2 4 1 2 4 1 2
5 3
3 2 3 2 1
10 4
4 3 4 3 2 3 2 1 0 1
15 7
3 7 4 8 2 3 4 5 21 2 3 4 2 1 3
7 5
1 2 3 4 5 6 1
Выходные данные
3 2
2 2
2 1
3 1
2 3
Примечание

В первом примере нужно выбрать отрезок гор со $$$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]$$$, поэтому они не являются правильным ответом.