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

玛丽安在一家赌场。赌场的游戏规则如下：

每轮开始前，玩家需选择一个介于 $1$ 和 $10^9$ 之间的整数。随后，一枚拥有 $10^9$ 个面的骰子被掷出，随机产生一个介于 $1$ 和 $10^9$ 之间的整数。若玩家猜中该数字，则其总金额翻倍；否则，其总金额减半。

玛丽安已预知未来，知晓接下来 $n$ 轮中骰子将依次显示的数字 $x_1, x_2, \dots, x_n$。

她将选定三个整数 $a$、$l$ 和 $r$（满足 $l \leq r$）。她将参与第 $l$ 轮至第 $r$ 轮（含端点），共 $r-l+1$ 轮。在这些轮次中，她每轮均猜测同一个数字 $a$。初始时（即第 $l$ 轮开始前），她拥有 $1$ 美元。

玛丽安请你确定整数 $a$、$l$ 和 $r$（满足 $1 \leq a \leq 10^9$，$1 \leq l \leq r \leq n$），使得她在所有轮次结束后获得的金额最大。

注意：在每次乘以 $2$ 或除以 $2$ 的过程中不进行任何舍入，且不存在精度误差。因此，例如，在游戏过程中，玛丽安的金额可能为 $\dfrac{1}{1024}$、$\dfrac{1}{128}$、$\dfrac{1}{2}$、$1$、$2$、$4$ 等（即任意形如 $2^t$ 的值，其中 $t$ 为任意整数，可正可负）。

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

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot 10^5$），表示轮数。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$1 \leq x_i \leq 10^9$），其中 $x_i$ 表示第 $i$ 轮中骰子掷出的数字。

保证所有测试用例的 $n$ 之和不超过 $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.

对于每个测试用例，输出三个整数 $a$、$l$ 和 $r$，使得 Marian 采用其策略进行赌博时能赚取最多的钱。如果存在多个答案，你可以输出其中任意一个。

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.

对于第一个测试用例，最优选择是 $a=4$、$l=1$、$r=5$，游戏过程如下：

• 玛丽安初始拥有 1 美元。
• 第一轮结束后，他拥有 2 美元，因为所出现的数字与选定的数字一致。
• 第二轮结束后，他拥有 4 美元，因为所出现的数字再次与选定的数字一致。
• 第三轮结束后，他拥有 2 美元，因为他猜了 $4$，但正确答案是 $3$。
• 第四轮结束后，他再次拥有 4 美元。
• 最后一轮结束后，他拥有 8 美元，因为他再次猜对了。

第二个测试用例存在多种可能的答案，但可以证明玛丽安最终拥有的金额不会超过 2 美元，因此任何满足 $l = r$ 且取适当 $a$ 的选择均可接受。