Wooden Raft
Contest: Technocup 2020 - Elimination Round 1
Difficulty rating: 3200
Tags: binary search, math, number theory

Suppose you are stuck on a desert island. The only way to save yourself is to craft a wooden raft and go to the sea. Fortunately, you have a hand-made saw and a forest nearby. Moreover, you've already cut several trees and prepared it to the point that now you have $$$n$$$ logs and the $$$i$$$-th log has length $$$a_i$$$.

The wooden raft you'd like to build has the following structure: $$$2$$$ logs of length $$$x$$$ and $$$x$$$ logs of length $$$y$$$. Such raft would have the area equal to $$$x \cdot y$$$. Both $$$x$$$ and $$$y$$$ must be integers since it's the only way you can measure the lengths while being on a desert island. And both $$$x$$$ and $$$y$$$ must be at least $$$2$$$ since the raft that is one log wide is unstable.

You can cut logs in pieces but you can't merge two logs in one. What is the maximum area of the raft you can craft?

Input format:
The first line contains the only integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of logs you have.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 5 \cdot 10^5$$$) — the corresponding lengths of the logs.

It's guaranteed that you can always craft at least $$$2 \times 2$$$ raft.

Output format:
Print the only integer — the maximum area of the raft you can craft.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can cut the log of the length $$$9$$$ in $$$5$$$ parts: $$$2 + 2 + 2 + 2 + 1$$$. Now you can build $$$2 \times 2$$$ raft using $$$2$$$ logs of length $$$x = 2$$$ and $$$x = 2$$$ logs of length $$$y = 2$$$.

In the second example, you can cut $$$a_4 = 18$$$ into two pieces $$$9 + 9$$$ and $$$a_8 = 28$$$ in three pieces $$$10 + 9 + 9$$$. Now you can make $$$10 \times 9$$$ raft using $$$2$$$ logs of length $$$10$$$ and $$$10$$$ logs of length $$$9$$$.

Example input:
1
9

Example output:
4

Example input:
9
9 10 9 18 9 9 9 28 9

Example output:
90

Editorial:
Let's iterate $$$y$$$ from $$$2$$$ to $$$A$$$, where $$$A = \max(a_i)$$$. And let's try to find the best answer for a fixed $$$y$$$ in $$$O(\frac{A}{y})$$$ time.
How to do so? At first, we can quite easily calculate the total number of logs of length $$$y$$$ we can acquire (denote it as $$$cntY$$$): since all $$$a_i \in [ky, ky + y)$$$ give the same number of logs which is equal to $$$k$$$, then let's just count the number of $$$a_i$$$ in $$$[ky, ky + y)$$$ for each $$$k$$$. We can do so using frequency array and prefix sums on it.
There are two cases in the problem: both logs of length $$$x$$$ lies in the same log $$$a_i$$$ or from the different logs $$$a_i$$$ and $$$a_j$$$. In the first case it's the same as finding one log of length $$$2x$$$. But in both cases we will divide all possible values of $$$x$$$ ($$$2x$$$) in segments $$$[ky, ky + y)$$$ and check each segment in $$$O(1)$$$ time.
Let's suppose that $$$2x \in [ky, ky + y)$$$ and there is $$$a_i$$$ such that $$$a_i \ge 2x$$$ and $$$(a_i \mod y) \ge (2x \mod y)$$$. In that case it's optimal to cut $$$2x$$$ from $$$a_i$$$ and, moreover, it's optimal to increase $$$2x$$$ while we can. It leads us straight to the solution, let's keep $$$\max(a_i \mod y)$$$ over $$$a_i \ge ky$$$ and check only $$$2x = ky + \max(a_i \mod y)$$$ (maybe minus one in case of wrong parity). We can maintain this max iterating $$$k$$$ in descending order. And since $$$\max(a_i \mod y)$$$ for all $$$a_i \in [ky, ky + y)$$$ is just a $$$\max(a_i~|~a_i < ky + y)$$$. We can find such $$$a_i$$$ in $$$O(1)$$$ using precalc. To check the chosen $$$2x$$$ is trivial: the number of remaining logs $$$y$$$ is equal to $$$cntY - k$$$ and the plot will have the area $$$y \cdot \min(x, cntY - k)$$$.
The case with cutting $$$x$$$-s from different $$$a_i$$$ and $$$a_j$$$ is based on the same idea, but we need to maintain two maximums $$$mx1$$$ and $$$mx2$$$ ($$$mx1 \ge mx2$$$). But in this case $$$x$$$ can be equal to both $$$mx1$$$ or $$$mx2$$$.
If $$$x = ky + mx2$$$ then everything is trivial: the number of logs $$$y$$$ is $$$cntY - 2 \cdot k$$$ and so on. If $$$x = ky + mx1$$$ then we need to additional check the existence of $$$a_i \ge x$$$ and $$$a_j \ge x$$$. Remaining number of logs $$$y$$$ will be equal to $$$cntY - 2 \cdot k - 1$$$ and so on.
In result, for each $$$y$$$ we can calculate the answer in $$$O(\frac{A}{y})$$$, so the total time complexity is $$$O(n + \sum_{y = 2}^{A}{O(\frac{A}{y})}) = O(n + A \log A)$$$.
P.S.: We decided to allow the $$$O(A \log^2 A)$$$ solution which binary search $$$x$$$ for each $$$y$$$ to pass if it's carefully written.