玛丽安在赌场。赌场的游戏是这样进行的。
每轮之前,玩家选择 $$$1$$$ 和 $$$10^9$$$ 之间的数字。之后,滚动一个面为 $$$10^9$$$ 的骰子,从而出现 $$$1$$$ 和 $$$10^9$$$ 之间的随机数。如果玩家猜对了数字,他们的总钱就会加倍,否则他们的总钱就会减半。
Marian 预测了未来,并且知道骰子在接下来的 $$$n$$$ 轮中将显示的所有数字 $$$x_1, x_2, \dots, x_n$$$。
他将选择三个整数 $$$a$$$、$$$l$$$ 和 $$$r$$$ ($$$l \leq r$$$)。他将打 $$$r-l+1$$$ 轮(包括 $$$l$$$ 和 $$$r$$$ 之间的轮次)。在每一轮中,他都会猜测相同的数字$$$a$$$。开始时(在 $$$l$$$ 回合之前)他有 $$$1$$$ 美元。
Marian 要求你确定整数 $$$a$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \leq a \leq 10^9$$$, $$$1 \leq l \leq r \leq n$$$),这样他最后赚的钱最多。
请注意,在减半和乘法过程中,没有舍入,也没有精度误差。因此,例如在游戏过程中,Marian 的资金可能等于 $$$\dfrac{1}{1024}$$$、$$$\dfrac{1}{128}$$$、$$$\dfrac{1}{2}$$$、$$$1$$$、$$$2$$$、$$$4$$$ 等($$$2^t$$$ 的任意值,其中 $$$t$$$ 是任何标志)。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出三个整数 $$$a$$$、$$$l$$$ 和 $$$r$$$,以便 Marian 通过他的策略赌博赚到最多的钱。如果有多个答案,您可以输出其中任何一个。
示例
输入 #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
注意
对于第一个测试用例,最佳选择是 $$$a=4$$$、$$$l=1$$$、$$$r=5$$$,游戏将如下进行。
- 玛丽安从一美元开始。
- 第一轮结束后,他最终获得了 $$$2$$$ 美元,因为数字与所选数字一致。
- 第二轮结束后,他最终获得了 $$$4$$$ 美元,因为数字再次重合。
- 第三轮结束后,他最终得到了 $$$2$$$ 美元,因为他猜测 $$$4$$$,尽管 $$$3$$$ 是正确的选择。
- 第四轮结束后,他再次获得 $$$4$$$ 美元。
- 在最后一轮中,他最终赢得了 $$$8$$$ 美元,因为他再次猜对了。
第二个测试用例有很多可能的答案,但可以证明 Marian 最终不会得到超过 $$$2$$$ 美元,因此 $$$l = r$$$ 以及适当的 $$$a$$$ 的任何选择都是可以接受的。