CF2153C.Symmetrical Polygons

You are given $n$ sticks, where the $i$-th stick has a length of $a_i$. You want to choose a non-empty subset of these sticks and use them as the sides of a polygon. Each selected stick must be used entirely as a single side of the polygon. It is not allowed for two or more sticks to be joined end-to-end in parallel to form a longer side.

Your goal is to form a polygon that is symmetrical, strictly convex, and non-degenerate:

• Symmetrical: there exists a line of symmetry such that when the polygon is folded along this line, the two halves coincide exactly.
• Strictly convex: all its internal angles are strictly less than $180^\circ$.
• Non-degenerate: no two consecutive sides coincide at least partially, no side has zero length, and no angle equals $180^\circ$.

Among all such polygons that you can form with the sticks, find the maximum possible perimeter$^{\text{∗}}$. If no valid polygon exists, output $0$.

$^{\text{∗}}$The perimeter of a polygon is equal to the sum of the lengths of its sides.

你有 $n$ 根木棍，其中第 $i$ 根木棍的长度为 $a_i$。你需要从中选出一个非空子集，并将这些木棍用作某个多边形的边。每根被选中的木棍必须完整地作为多边形的一条边使用；不允许将两根或更多木棍首尾相连（并联）以构成更长的一条边。

你的目标是构造一个对称的、严格凸的、非退化的多边形：

• 对称的：存在一条对称轴，使得该多边形沿此轴对折后，两半完全重合。
• 严格凸的：所有内角均严格小于 $180^\circ$。
• 非退化的：任意两条相邻边不部分重合，任意边长度不为零，且任意内角不等于 $180^\circ$。

在所有能用给定木棍构造出的满足上述条件的多边形中，求其最大可能的周长$^{\text{∗}}$。若不存在任何合法多边形，则输出 $0$。

$^{\text{∗}}$多边形的周长等于其所有边长之和。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3\le n\le 2\cdot 10^5$) — the number of sticks.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 10^9$) — the lengths of the sticks.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3\le n\le 2\cdot 10^5$）—— 表示木棍的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 10^9$）—— 表示各木棍的长度。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

For each test case, output a single integer representing the maximum possible perimeter of a non-degenerate, symmetrical and strictly convex polygon that you can form from a non-empty subset of the sticks. If it is not possible, output $0$.

对于每个测试用例，输出一个整数，表示从木棍的非空子集中所能构成的非退化、对称且严格凸多边形的最大可能周长；若无法构成，输出 $0$。

In the first test case, you can form an isosceles triangle using all three sticks. It is symmetrical along the vertical dotted line (see left diagram). The perimeter is equal to the sum of the lengths of its sides: $5 + 5 + 7 = 17$.

In the second test case, the triangle formed by all three sticks is not symmetrical (see right diagram). It can be proven that no symmetrical, non-degenerate convex polygon can be formed from any non-empty subset of the sticks.

In the third test case, it is not possible to form a non-degenerate polygon. If all three sides are used, the two sides of length $5$ coincide with the side of length $10$, producing only a straight line with zero area.

In the fourth test case, we can form a symmetrical convex polygon using three sticks of length $3$, two sticks of length $5$, and one stick of length $4$ (see left diagram). The last stick of length $1$ cannot be included, as the resulting polygon would no longer be symmetrical (see right diagram).

In the fifth test case, it is not allowed to join the sticks of length $2$ and $3$ to form a stick of length $5$ (which would yield the first test case). It can be proven that no symmetrical, non-degenerate convex polygon can be formed from any non-empty subset of the sticks.

在第一个测试用例中，你可以使用全部三根木棍构成一个等腰三角形。该三角形关于竖直虚线对称（见左图）。其周长等于各边长度之和：$5 + 5 + 7 = 17$。

在第二个测试用例中，由全部三根木棍构成的三角形不具有对称性（见右图）。可以证明：无法从木棍的任意非空子集中构造出任何对称的、非退化的凸多边形。

在第三个测试用例中，无法构成非退化多边形。若使用全部三条边，则两条长度为 $5$ 的边将与长度为 $10$ 的边重合，仅形成一条面积为零的直线段。

在第四个测试用例中，我们可以使用三根长度为 $3$ 的木棍、两根长度为 $5$ 的木棍以及一根长度为 $4$ 的木棍，构成一个对称的凸多边形（见左图）。最后一根长度为 $1$ 的木棍不能被包含在内，否则所得多边形将不再对称（见右图）。

在第五个测试用例中，不允许将长度为 $2$ 和 $3$ 的木棍拼接成一根长度为 $5$ 的木棍（否则将退化为第一个测试用例）。可以证明：无法从木棍的任意非空子集中构造出任何对称的、非退化的凸多边形。