Maximizing Triangle Area with Wooden Boards

Hei, the cow architect, wants to build a triangular pasture enclosed by a beautiful white picket fence. She has n wooden boards, each with an integer length \(l_i\). She intends to use all these boards to form the three sides of a triangle such that the area is maximized.

Let the three sides of the triangle be \(A\), \(B\), and \(C\) where \(A+B+C=S\) is the total length of all boards. A triangle is valid if it satisfies the triangle inequalities: \[ A+B > C, \quad A+C > B, \quad B+C > A. \] The area of a valid triangle can be computed by Heron’s formula: \[ s=\frac{A+B+C}{2}, \quad Area = \sqrt{s(s-A)(s-B)(s-C)}. \] If no valid triangle can be formed, the maximum area is defined as 0.

Your task is to partition the boards into 3 groups (each group forming one side) using all boards, so that the area of the resulting triangle is maximized. Note that the board lengths cannot be changed and each board must be used exactly once.

inputFormat

The first line contains a single integer n representing the number of boards. The second line contains n space-separated integers, each denoting the length \(l_i\) of a board.

outputFormat

Output a single number representing the maximum area of the triangle that can be formed, with at least 6 decimal places of precision. If no valid triangle can be formed, output 0.

sample

3
3 4 5

6.000000