Gambling

题意翻译

### 题目描述 Marian 在一个赌场，赌场的游戏规则如下： 每一轮开始前，玩家选一个在 $1$ 到 $10^9$ 。然后，掷出一个有着 $10^9$ 面的骰子，会随机出现一个在 $1$ 与 $10^9$ 之间的数。如果玩家猜对了，他们的钱就会翻一番，否则他们的钱会被折半。 Marian 可以预测未来，他知道在接下来 $n$ 轮里骰子上的数，即 $x_1,x_2,...,x_n$。 Marian 会选择三个整数 $a,l$ 和 $r$（$l \le r$）。他会玩 $r-l+1$ 轮。每一轮，他都猜同一个数 $a$。一开始（在第 $l$ 轮之前）他有 $1$ 美元。 Marian 请你帮助他决定 $a,l$ 和 $r$（$1\le a\le 10^9,1\le l\le r\le n$），让他最后的钱最多。 注：在折半或翻番的过程中不会进行游戏，也不会有精度问题。举个例子，Marian 在游戏中可能会有 $\frac{1}{1024},\frac{1}{128},\frac{1}{2},1,2,4$ 等等（任何可以表示为 $2^t$ 的数，其中 $t$ 为非 $0$ 整数）。 ### 输入格式 第一行包含一个整数 $t$（$1\le t\le 100$），即数据的组数。 每组数据的第一行包含一个整数 $n$（$1\le n\le 2\times 10^5$）。 每组数据的第二行包含 $n$ 个整数 $x_1,x_2...x_n$（$1\le x_i\le 10^9$），$x_i$ 表示骰子在第 $i$ 轮掷出的数字。 数据保证所有数据中的 $n$ 之和不大于 $2\times 10^5$。 ### 输出格式 每组数据输出三个整数 $a,l$ 与 $r$，使得 Marian 能得到最多的钱。如果有多个答案，可以输出它们中的任意一个。 ### 说明/提示 对于第一组数据，最好的选择是 $a=4,l=1,r=5$，游戏会这样进行： - Marian 最开始有 $1$ 美元。 - 第一轮结束后，Marian 会有 $2$ 美元，因为骰子上掷出的数与 Marian 猜的数相同。 - 第二轮结束后，Marian 会有 $4$ 美元，因为他又猜对了。 - 第三轮结束后，Marian 会有 $2$ 美元，因为他猜了 $4$，而 $3$ 是正确答案。 - 第四轮结束后，Marian 又会有 $4$ 美元，因为他又又猜对了。 - 最后一轮结束后，Marian 会 $8$ 美元，因为他又又又猜对了。 第二组数据有多种答案，但可以证明 Marian 最后最多只有 $2$ 美元，因此只要 $l=r$ 且 $a$ 的数字合理，都是正确答案

题目描述

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.

输入输出样例

输入样例 #1

4
5
4 4 3 4 4
5
11 1 11 1 11
1
1000000000
10
8 8 8 9 9 6 6 9 6 6

输出样例 #1

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

**题目大意：**

Marian 在一个赌场玩一个游戏，游戏规则如下：

- 每一轮开始前，玩家选择一个 $1$ 到 $10^9$ 之间的数。
- 然后，掷出一个有 $10^9$ 面的骰子，随机出现一个 $1$ 到 $10^9$ 之间的数。
- 如果玩家猜对了，他们的钱就会翻一番；否则，他们的钱会被折半。

Marian 可以预测未来，他知道接下来 $n$ 轮骰子上的数，即 $x_1,x_2,...,x_n$。

Marian 会选择三个整数 $a, l$ 和 $r$（$l \le r$），他会玩 $r-l+1$ 轮。每一轮，他都猜同一个数 $a$。一开始（在第 $l$ 轮之前）他有 $1$ 美元。

你的任务是帮助Marian决定 $a, l$ 和 $r$（$1 \le a \le 10^9, 1 \le l \le r \le n$），以使最后的钱最多。

**输入输出数据格式：**

**输入格式：**

- 第一行包含一个整数 $t$（$1 \le t \le 100$），即数据的组数。
- 每组数据的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。
- 每组数据的第二行包含 $n$ 个整数 $x_1,x_2,...,x_n$（$1 \le x_i \le 10^9$），$x_i$ 表示骰子在第 $i$ 轮掷出的数字。
- 保证所有数据中的 $n$ 之和不大于 $2 \times 10^5$。

**输出格式：**

- 对于每组数据，输出三个整数 $a, l$ 和 $r$，使得Marian能得到的钱最多。如果有多个答案，可以输出它们中的任意一个。**题目大意：** Marian 在一个赌场玩一个游戏，游戏规则如下： - 每一轮开始前，玩家选择一个 $1$ 到 $10^9$ 之间的数。 - 然后，掷出一个有 $10^9$ 面的骰子，随机出现一个 $1$ 到 $10^9$ 之间的数。 - 如果玩家猜对了，他们的钱就会翻一番；否则，他们的钱会被折半。 Marian 可以预测未来，他知道接下来 $n$ 轮骰子上的数，即 $x_1,x_2,...,x_n$。 Marian 会选择三个整数 $a, l$ 和 $r$（$l \le r$），他会玩 $r-l+1$ 轮。每一轮，他都猜同一个数 $a$。一开始（在第 $l$ 轮之前）他有 $1$ 美元。 你的任务是帮助Marian决定 $a, l$ 和 $r$（$1 \le a \le 10^9, 1 \le l \le r \le n$），以使最后的钱最多。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $t$（$1 \le t \le 100$），即数据的组数。 - 每组数据的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。 - 每组数据的第二行包含 $n$ 个整数 $x_1,x_2,...,x_n$（$1 \le x_i \le 10^9$），$x_i$ 表示骰子在第 $i$ 轮掷出的数字。 - 保证所有数据中的 $n$ 之和不大于 $2 \times 10^5$。 **输出格式：** - 对于每组数据，输出三个整数 $a, l$ 和 $r$，使得Marian能得到的钱最多。如果有多个答案，可以输出它们中的任意一个。