H. Азартные игры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мариан пришёл в казино. Игры в казино проходят следующим образом.

Перед каждым раундом игрок выбирает число от $$$1$$$ до $$$10^9$$$. После этого бросается игральная кость с $$$10^9$$$ сторонами, и выпадает случайное число от $$$1$$$ до $$$10^9$$$. Если игрок угадал выпавшее число, количество его денег удваивается, в противном случае количество его денег уменьшается вдвое.

Мариан умеет предсказывать будущее, поэтому он знает все числа $$$x_1, x_2, \dots, x_n$$$ которые выпадут на игральной кости в следующих $$$n$$$ раундах.

Мариан хочет выбрать три числа $$$a$$$, $$$l$$$, $$$r$$$ ($$$l \leq r$$$). Он будет играть $$$r-l+1$$$ раунд (раунды с номерами от $$$l$$$ до $$$r$$$). В каждом из этих раундов он будет загадывать одно и тоже число $$$a$$$. На старте (перед раундом $$$l$$$) у него $$$1$$$ доллар.

Мариан просит вас найти такие $$$a$$$, $$$l$$$ и $$$r$$$ ($$$1 \leq a \leq 10^9$$$, $$$1 \leq l \leq r \leq n$$$) таких, что в конце игры у него будет максимальная сумма денег.

Заметьте, что при проигрыше или выигрыше (т.е. уменьшении или увеличении количества денег вдвое) количество денег не округляется. Все операции деления/умножения проводятся с бесконечной точностью. Например, во время игры Мариан может иметь количество денег, равное $$$\dfrac{1}{1024}$$$, $$$\dfrac{1}{128}$$$, $$$\dfrac{1}{2}$$$, $$$1$$$, $$$2$$$, $$$4$$$, и т.д. (любое значение $$$2^t$$$, где $$$t$$$ — целое число любого знака).

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) — количество раундов в игре.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$), где $$$x_i$$$ — число, которое выпадет на игральной кости в $$$i$$$-м раунде.

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

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

Для каждого набора выведите три числа — $$$a$$$, $$$l$$$, и $$$r$$$ таких, что выигрыш Мариана в казино будет максимальным. Если существует несколько различных ответов, вы можете вывести любой из них.

Пример
Входные данные
4
5
4 4 3 4 4
5
11 1 11 1 11
1
1000000000
10
8 8 8 9 9 6 6 9 6 6
Выходные данные
4 1 5
1 2 2
1000000000 1 1
6 6 10
Примечание

В первом наборе лучшим выбором будет $$$a=4$$$, $$$l=1$$$, $$$r=5$$$. Игра пройдёт следующим образом:

  • Мариан начинает игру с одним долларом.
  • После первого раунда у Мариана будет $$$2$$$ доллара, так как он угадал выпавшее число.
  • После второго раунда у Мариана будет $$$4$$$ доллара, так как он вновь угадал выпавшее число.
  • После третьего раунда у Мариана будет $$$2$$$ доллара, так как он загадал $$$4$$$, а выпало число $$$3$$$.
  • После четвертого раунда у Мариана вновь будет $$$4$$$ доллара.
  • В последнем раунде Мариан закончит с $$$8$$$ долларами, так как он вновь угадал выпавшее число.

Для второго набора есть много подходящих ответов, однако можно доказать что Мариан не может закончить играть с более чем $$$2$$$ долларами, так что любой выбор $$$l = r$$$ с подходящим $$$a$$$ будет приемлемым.