A15080 | Gambling

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.