← 返回题目列表

Codeforces · 1223/G

G. 木筏

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

假设你被困在一个荒岛上。拯救自己的唯一方法就是制作木筏并出海。幸运的是,您有一把手工锯和附近的一片森林。此外,您已经砍伐了几棵树并准备好,现在您有 $$$n$$$ 日志,并且第 $$$i$$$ 日志的长度为 $$$a_i$$$。

您要建造的木筏具有以下结构:$$$2$$$ 长度为 $$$x$$$ 的原木和 $$$x$$$ 长度为 $$$y$$$ 的原木。这样的筏的面积等于 $$$x \cdot y$$$。 $$$x$$$ 和 $$$y$$$ 都必须是整数,因为这是在荒岛上测量长度的唯一方法。 $$$x$$$ 和 $$$y$$$ 都必须至少为 $$$2$$$,因为一根圆木宽的木筏是不稳定的。

你可以将原木切成碎片,但不能将两根原木合二为一。您可以制作的木筏的最大面积是多少?

输入

第一行包含唯一的整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 您拥有的日志数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 5 \cdot 10^5$$$) — 对应的日志长度。

保证您始终可以制作至少 $$$2 \times 2$$$ 木筏。

输出

打印唯一的整数 - 您可以制作的木筏的最大面积。

示例

输入 #1

1
9

输出 #1

4

输入 #2

9
9 10 9 18 9 9 9 28 9

输出 #2

90

注意

在第一个示例中,您可以将长度为 $$$9$$$ 的日志切割为 $$$5$$$ 部分:$$$2 + 2 + 2 + 2 + 1$$$。现在您可以使用 $$$2$$$ 长度为 $$$x = 2$$$ 的原木和 $$$x = 2$$$ 长度为 $$$y = 2$$$ 的原木建造 $$$2 \times 2$$$ 筏。

在第二个示例中,您可以将 $$$a_4 = 18$$$ 切成两块 $$$9 + 9$$$ 并将 $$$a_8 = 28$$$ 切成三块 $$$10 + 9 + 9$$$。现在,您可以使用长度为 $$$10$$$ 的 $$$2$$$ 圆木和长度为 $$$9$$$ 的 $$$10$$$ 圆木制作 $$$10 \times 9$$$ 筏。