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 \leq 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 \leq a \leq 10^9$, $1 \leq l \leq r \leq 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 $\dfrac{1}{1024}$, $\dfrac{1}{128}$, $\dfrac{1}{2}$, $1$, $2$, $4$, etc. (any value of $2^t$, where $t$ is an integer of any sign).

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

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 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 \leq x_i \leq 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\cdot10^5$.

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.