← 返回题目列表

Codeforces · 1617/E

E. 圣诞巧克力

中文机器翻译题面 查看原题

圣诞节快到了,Icy刚刚收到祖父母寄来的一盒巧克力!盒子里装着 $$$n$$$ 巧克力。第 $$$i$$$ 巧克力具有非负整数类型 $$$a_i$$$。

Icy相信好事成双。不幸的是,所有类型的巧克力都是不同的(所有 $$$a_i$$$ 都是不同的)。 Icy 想要制作至少一对相同类型的巧克力。

因此,她要求祖父母进行一些巧克力交换。在进行任何巧克力交换之前,Icy 选择两种索引为 $$$x$$$ 和 $$$y$$$ 的巧克力($$$1 \le x, y \le n$$$, $$$x \ne y$$$)。

在一次巧克力交换中,Icy的祖父母选择一个非负整数$$$k$$$,使得$$$2^k \ge a_x$$$,并将巧克力$$$x$$$的类型从$$$a_x$$$更改为$$$2^k - a_x$$$(即执行$$$a_x := 2^k - a_x$$$)。

仅当$$$a_x = a_y$$$时,巧克力交换才会停止。请注意,其他对相同类型的巧克力不会停止该过程。

Icy 的祖父母很聪明,所以他们会选择巧克力交换的顺序,以尽量减少所需交换的次数。由于 Icy 喜欢制造麻烦,她希望通过适当选择 $$$x$$$ 和 $$$y$$$ 来最大化所需的最少交换次数。她想知道什么是最佳的 $$$(x, y)$$$ 配对,以便在 $$$(x, y)$$$ 的所有可能选择中最大化所需的最少交换次数。

由于Icy不擅长数学,她希望你能帮她解决这个问题。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 巧克力的数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

保证所有 $$$a_i$$$ 都是不同的。

输出

输出三个整数 $$$x$$$、$$$y$$$ 和 $$$m$$$。

$$$x$$$ 和 $$$y$$$ 是要进行交换的最佳巧克力的索引。您的输出必须满足 $$$1 \le x, y \le n$$$, $$$x \ne y$$$。

$$$m$$$ 是获得$$$a_x = a_y$$$ 所需的交换次数。我们可以证明任何一对巧克力的 $$$m \le 10^9$$$ 。

如果有多个解,则输出任意一个。

示例

输入 #1

5
5 6 7 8 9

输出 #1

2 5 5

输入 #2

2
4 8

输出 #2

1 2 2

注意

在第一个测试用例中,将 $$$6$$$ 类型的巧克力交换为 $$$9$$$ 类型的巧克力所需的最少交换次数为 $$$5$$$。交换顺序如下:$$$6 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 7 \rightarrow 9$$$。

在第二个测试用例中,将 $$$4$$$ 类型的巧克力交换为 $$$8$$$ 类型的巧克力所需的最少交换次数为 $$$2$$$。交换顺序如下:$$$4 \rightarrow 0 \rightarrow 8$$$。