AT_utpc2023_l.Largest Triangle

有 $N$ 根直棒。第 $i$ 根棒的长度为 $L_i$。

从这些棒中选出 $3$ 根，将它们作为三角形的三条边（要求三角形非退化且三边能组成三角形）。请判断是否存在这种选择方法；如果存在，请求出可以组成的三角形的面积的最大值的平方。

有 $T$ 组测试数据，请分别作答。

输入由标准输入按如下格式给出，这里 $\mathrm{case}_i$ 表示第 $i$ 个测试用例。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每组测试数据的格式如下：

$N$ $L_1$ $L_2$ $\dots$ $L_N$

输出共 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

对于每组测试数据，如果不存在满足条件的三根棒，则输出 $-1$。如果存在，请输出可以组成的三角形的最大面积的平方，结果为整数（可以证明在本题范围下结果为整数）。

样例解释 1

对于第 $2$ 组测试数据，能组成最大三角形的三条边长度为 $8, 10, 10$，该三角形的面积为 $8\sqrt{21}$，面积的平方为 $1344$。

对于第 $3$ 组测试数据，无论选哪三根棒都无法组成三角形。

数据范围

• 输入均为整数。
• $1 \leq T \leq 2 \times 10^5$
• $3 \leq N \leq 2 \times 10^5$
• $2 \leq L_i \leq 20000$
• $L_i$ 为偶数
• 所有测试数据中 $N$ 的总和不超过 $2 \times 10^5$。

由 ChatGPT 5 翻译