CF1692H 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.

For the first test case, the best choice is $ a=4 $ , $ l=1 $ , $ r=5 $ , and the game would go as follows. - Marian starts with one dollar. - After the first round, he ends up with $ 2 $ dollars because the numbers coincide with the chosen one. - After the second round, he ends up with $ 4 $ dollars because the numbers coincide again. - After the third round, he ends up with $ 2 $ dollars because he guesses $ 4 $ even though $ 3 $ is the correct choice. - After the fourth round, he ends up with $ 4 $ dollars again. - In the final round, he ends up $ 8 $ dollars because he again guessed correctly. There are many possible answers for the second test case, but it can be proven that Marian will not end up with more than $ 2 $ dollars, so any choice with $ l = r $ with the appropriate $ a $ is acceptable.