## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Gambling Codeforces Solution | Codeforces Problem Solution 2022

H. Gambling
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Marian is at a casino. The game at the casino works like this.

Before each round, the player selects a number between $1$ and ${10}^{9}$. After that, a dice with ${10}^{9}$ faces is rolled so that a random number between $1$ and ${10}^{9}$ appears. If the player guesses the number correctly their total money is doubled, else their total money is halved.

Marian predicted the future and knows all the numbers ${x}_{1},{x}_{2},\dots ,{x}_{n}$ that the dice will show in the next $n$ rounds.

He will pick three integers $a$$l$ and $r$ ($l\le r$). He will play $r-l+1$ rounds (rounds between $l$ and $r$ inclusive). In each of these rounds, he will guess the same number $a$. At the start (before the round $l$) he has $1$ dollar.

Marian asks you to determine the integers $a$$l$ and $r$ ($1\le a\le {10}^{9}$$1\le l\le r\le n$) such that he makes the most money at the end.

Note that during halving and multiplying there is no rounding and there are no precision errors. So, for example during a game, Marian could have money equal to $\frac{1}{1024}$$\frac{1}{128}$$\frac{1}{2}$$1$$2$$4$, etc. (any value of ${2}^{t}$, where $t$ is an integer of any sign).

Input

The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot {10}^{5}$) — the number of rounds.

The second line of each test case contains $n$ integers ${x}_{1},{x}_{2},\dots ,{x}_{n}$ ($1\le {x}_{i}\le {10}^{9}$), where ${x}_{i}$ is the number that will fall on the dice in the $i$-th round.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot {10}^{5}$.

Output

For each test case, output three integers $a$$l$, and $r$ such that Marian makes the most amount of money gambling with his strategy. If there are multiple answers, you may output any of them.