Christmas Chocolates
Contest: Codeforces Round 761 (Div. 2)
Difficulty rating: 2700
Tags: dfs and similar, dp, games, graphs, implementation, math, number theory, shortest paths, trees

Christmas is coming, Icy has just received a box of chocolates from her grandparents! The box contains $$$n$$$ chocolates. The $$$i$$$-th chocolate has a non-negative integer type $$$a_i$$$.

Icy believes that good things come in pairs. Unfortunately, all types of chocolates are distinct (all $$$a_i$$$ are distinct). Icy wants to make at least one pair of chocolates the same type.

As a result, she asks her grandparents to perform some chocolate exchanges. Before performing any chocolate exchanges, Icy chooses two chocolates with indices $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$).

In a chocolate exchange, Icy's grandparents choose a non-negative integer $$$k$$$, such that $$$2^k \ge a_x$$$, and change the type of the chocolate $$$x$$$ from $$$a_x$$$ to $$$2^k - a_x$$$ (that is, perform $$$a_x := 2^k - a_x$$$).

The chocolate exchanges will be stopped only when $$$a_x = a_y$$$. Note that other pairs of equal chocolate types do not stop the procedure.

Icy's grandparents are smart, so they would choose the sequence of chocolate exchanges that minimizes the number of exchanges needed. Since Icy likes causing trouble, she wants to maximize the minimum number of exchanges needed by choosing $$$x$$$ and $$$y$$$ appropriately. She wonders what is the optimal pair $$$(x, y)$$$ such that the minimum number of exchanges needed is maximized across all possible choices of $$$(x, y)$$$.

Since Icy is not good at math, she hopes that you can help her solve the problem.

Input format:
The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of chocolates.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

It is guaranteed that all $$$a_i$$$ are distinct.

Output format:
Output three integers $$$x$$$, $$$y$$$, and $$$m$$$.

$$$x$$$ and $$$y$$$ are indices of the optimal chocolates to perform exchanges on. Your output must satisfy $$$1 \le x, y \le n$$$, $$$x \ne y$$$.

$$$m$$$ is the number of exchanges needed to obtain $$$a_x = a_y$$$. We can show that $$$m \le 10^9$$$ for any pair of chocolates.

If there are multiple solutions, output any.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the minimum number of exchanges needed to exchange a chocolate of type $$$6$$$ to a chocolate of type $$$9$$$ is $$$5$$$. The sequence of exchanges is as follows: $$$6 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 7 \rightarrow 9$$$.

In the second test case, the minimum number of exchanges needed to exchange a chocolate of type $$$4$$$ to a chocolate of type $$$8$$$ is $$$2$$$. The sequence of exchanges is as follows: $$$4 \rightarrow 0 \rightarrow 8$$$.

Example input:
5
5 6 7 8 9

Example output:
2 5 5

Example input:
2
4 8

Example output:
1 2 2

Editorial:
Key observation: For any $$$i \ge 1$$$, there exists only one $$$j$$$ ($$$0 \le j < i$$$) such that $$$i + j = 2^k$$$ for some $$$k \ge 0$$$.
The proof is as follows: let's say that $$$0 \le j_1, j_2 < i$$$, $$$j_1 \ge j_2$$$, $$$i + j_1 = 2^{k_1}$$$, $$$i + j_2 = 2^{k_2}$$$. Then, $$$j_1 - j_2 = 2^{k_2} \cdot (2^{k_1-k_2} - 1)$$$. So, $$$j_1 \equiv j_2 \pmod {2^{k_2}}$$$. Since $$$i \le 2^{k_2}$$$, $$$j_1 = j_2$$$.
Then, we realize we can build a graph as follows: add an edge between $$$x$$$ and $$$y$$$ ($$$x, y \ge 0$$$) if $$$x + y = 2^k$$$ for some $$$k \ge 0$$$. Because of the first key observation, the graph must be a tree. We can root the tree at node $$$0$$$.
Our problem is equivalent to finding the pair of nodes which have maximum distance in a tree, which can be solved using the diameter of tree algorithm.
Since $$$0 \le a_i \le 10^9$$$, it is impossible to build the entire tree. A final observation is that: Consider any node $$$v$$$ with degree $$$\ge 2$$$ in the tree, then $$$v > p_v$$$ and $$$p_v > p_{p_v}$$$, therefore $$$v + p_v > p_v + p_{p_v}$$$ ($$$p_x$$$ denotes the parent of node $$$x$$$ in the tree).
Hence the depth of the tree is $$$\lceil \log(max(a_i)) \rceil = 30$$$, since there are only $$$\lceil \log(max(a_i)) \rceil$$$ possible $$$k$$$ ($$$0 \le k < 30$$$) for the sum of two nodes connected by an edge.
So, there are two ways to do it: the first way is to build parts of the tree: only the $$$n$$$ given nodes and the ancestors of the $$$n$$$ nodes. There will be at most $$$O(n \log max(a_i))$$$ nodes, which should fit into the memory limit. The second way is to not build the tree at all, and calculate the LCA (Lowest Common Ancestor) of two nodes to find their distance. Since the depth of the tree is $$$30$$$, LCA of two nodes can be computed by simply checking every ancestor of both nodes.
In both ways, the time complexity is $$$O(n \log max(a_i))$$$.