Codeforces Round 799 (Div. 4) |
---|
Finished |
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.
454 4 3 4 4511 1 11 1 1111000000000108 8 8 9 9 6 6 9 6 6
4 1 5 1 2 2 1000000000 1 1 6 6 10
For the first test case, the best choice is $$$a=4$$$, $$$l=1$$$, $$$r=5$$$, and the game would go as follows.
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.
Name |
---|