E1. Подмедианы (легкая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это легкая версия задачи. Единственное отличие заключается в том, что в этой версии вам нужно найти подмассив только для максимальной подмедианы.

Вы можете делать взломы только в том случае, если обе версии задачи решены.

Целое число $$$v$$$ является медианой массива $$$b$$$ длины $$$m$$$ тогда и только тогда, когда:

  • $$$v$$$ больше или равно как минимум $$$\lceil \frac{m}{2} \rceil$$$ элементов массива, и
  • $$$v$$$ меньше или равно как минимум $$$\lceil \frac{m}{2} \rceil$$$ элементов массива.
Например:
  • единственной медианой массива $$$[9, 3, 7]$$$ является $$$7$$$,
  • медианами массива $$$[5, 3, 7, 9]$$$ являются $$$5$$$, $$$6$$$ и $$$7$$$, и
  • единственной медианой массива $$$[2, 2, 2]$$$ является $$$2$$$.

Вам дано целое число $$$k$$$ и массив $$$a_1, \ldots, a_n$$$ целых чисел от $$$1$$$ до $$$n$$$.

Целое число $$$v$$$ от $$$1$$$ до $$$n$$$ называется подмедианой, если существует хотя бы одна пара индексов $$$(l, r)$$$ такая, что

  • $$$1 \leq l \leq r \leq n$$$,
  • $$$r - l + 1 \geq k$$$,
  • $$$v$$$ является медианой подмассива $$$[a_l, \ldots, a_r]$$$.

Можно доказать, что всегда существует хотя бы одна подмедиана. Найдите максимальную подмедиану $$$v_\max$$$ и любую соответствующую пару индексов $$$(l, r)$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого теста содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 300\,000$$$).

Вторая строка каждого теста содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$300\,000$$$.

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

Для каждого теста выведите три целых числа $$$v_\max$$$, $$$l$$$ и $$$r$$$ — максимальная подмедиана $$$v_\max$$$ и границы подмассива длиной хотя бы $$$k$$$ ($$$r - l + 1 \geq k$$$), такой что $$$v_\max$$$ является одной из его медиан.

Если существует несколько решений, вы можете вывести любое из них.

Пример
Входные данные
7
4 3
4 1 2 4
5 2
1 2 3 2 1
5 3
1 2 3 2 1
5 3
1 1 2 5 3
1 1
1
2 1
2 1
4 1
1 2 1 3
Выходные данные
4 1 4
3 3 4
2 2 4
3 3 5
1 1 1
2 1 2
3 4 4
Примечание

В первом тесте подмассивы длиной хотя бы $$$k = 3$$$:

  • $$$(l = 1, r = 3)$$$: $$$[4, 1, 2]$$$, медиана которого равна $$$2$$$,
  • $$$(l = 2, r = 4)$$$: $$$[1, 2, 4]$$$, медиана которого равна $$$2$$$, и
  • $$$(l = 1, r = 4)$$$: $$$[4, 1, 2, 4]$$$, медианами которого являются $$$2$$$, $$$3$$$ и $$$4$$$.

Во втором тесте одним из возможных ответов является $$$(l = 3, r = 4)$$$, медианами которого являются $$$2$$$ и $$$3$$$.

Обратите внимание, что можно доказать, что ни один подмассив длиной хотя бы $$$2$$$ не имеет $$$4$$$ или $$$5$$$ в качестве медианы.