Problem Description

In a mysterious forest, there lives a little elf named Xiao Lan. One day, he accidentally discovered a treasure hidden in a tree hole, filled with gems that sparkle with beautiful light. These gems have different colors and shapes, but the most eye-catching part is their unique “shininess” attribute. Each gem is born with a special ability to emit flashes of different intensities. Xiao Lan found a total of $n$ gems. The “shininess” attribute value of the $i$-th gem is $H_i$. Xiao Lan will choose three gems from these $n$ gems to form a combination. The beauty level $S$ after combining can be measured by the following formula:

$$S = H_a H_b H_c \cdot \frac{\operatorname{LCM}(H_a, H_b, H_c)}{\operatorname{LCM}(H_a, H_b) \cdot\operatorname{LCM}(H_a, H_c) \operatorname{LCM}(H_b, H_c)}$$

Here, $\operatorname{LCM}$ denotes the least common multiple function.

Xiao Lan wants the beauty level $S$ of the three-gem combination to be as high as possible. Please help him find the plan with the maximum beauty level. If there are multiple plans with the same $S$, choose the one that is lexicographically smallest after sorting the three $H$ values in ascending order first.

Input Format

The first line contains an integer $n$, representing the number of gems.
The second line contains $n$ integers $H_1, H_2, \dots H_n$, representing the shininess of each gem.

Output Format

Output one line containing three integers, representing the “shininess” of the three gems that satisfy the conditions.

5
1 2 3 4 9

1 2 3

Hint

Constraints

• For $30\%$ of the data, $n \leq 100$, $H_i \leq 10^3$.
• For $60\%$ of the data, $n \leq 2 \times 10^3$.
• For all testdata, it is guaranteed that $3 \leq n \leq 10^5$, $1 \leq H_i \leq 10^5$.

Translated by ChatGPT 5