Symmetrical Polygons

The problem looks geometric, but the actual fight is with parity. The diagrams are basically screaming: matched sides come in mirrored pairs, and the symmetry axis can only “own” a tiny number of sides.

Key Geometry Fact

In a reflection-symmetric strictly convex polygon:

• every side not fixed by the reflection is matched with another side of the same length;
• the reflection axis can fix at most two sides.

Why at most two? A line can enter and leave a strictly convex polygon only once, so it can touch the boundary in at most two boundary pieces. No weird zig-zag nonsense is possible in a strictly convex polygon.

So any valid selected subset has this shape:

• any number of equal-length pairs;
• plus at most two unpaired sticks.

That means after pairing equal lengths, we are allowed to keep at most two leftovers.

There is one more condition: the selected side lengths must actually form a non-degenerate polygon. For positive side lengths, that is exactly the strict polygon inequality:

$$\max(s_i) < \sum s_i - \max(s_i)$$

In English: the longest side must be shorter than all the other sides combined. Equality is the annoying “flat line” case, like $5,5,10$, and it is invalid.

Why We Take All Pairs

Group equal lengths. For every length $x$ with frequency $c$, take $\lfloor c/2\rfloor$ pairs. Let

$$P = \text{sum of all sticks used in these pairs}.$$

Taking a pair is always good:

• it adds perimeter;
• it does not consume one of the two unpaired slots;
• it makes the polygon inequality easier because it adds two equal sides.

So the optimal answer always starts with all possible pairs. The only choice is which leftover odd-frequency sticks to add.

Let the leftover list be $b_1,b_2,\dots,b_m$.

If there are no paired sticks at all, answer is $0$. With only one or two unpaired sticks you cannot make a polygon. Geometry is not magic; two sticks is just sadness.

Choosing Zero Leftovers

Using only pairs is valid if we have at least two pairs. One pair gives only two sides, so no polygon.

So candidate:

$$P \quad \text{if number of pairs} \ge 2$$

Choosing One Leftover

Suppose we add one leftover stick of length $x$.

The only dangerous case is when $x$ is the longest side. Then we need

$$x < P$$

If $x$ is not the longest side, the paired sides already balance themselves, so we are fine. The same condition $x<P$ captures the real danger.

Candidate:

$$P+x \quad \text{if } x<P$$

This handles isosceles triangles too. Example: $5,5,7$ has $P=10$, and $7<10$, so perimeter $17$.

Choosing Two Leftovers

Suppose we add two leftovers $x\le y$.

Again, the only real danger is the larger leftover $y$. The paired part contributes total length $P$, and the other leftover contributes $x$, so we need

$$y < P+x$$

Equivalently:

$$y-x < P$$

We want to maximize $x+y$. Sort the leftovers. For a fixed larger value $y=b_i$, the best smaller partner is just the previous leftover $b_{i-1}$, because it is the largest possible $x$. If $b_i-b_{i-1}\ge P$, then every even smaller partner is worse and also fails.

So it is enough to check adjacent leftover pairs.

Algorithm

For each test case:

1. Sort the array.
2. Scan equal-value groups.
3. Add all possible pairs to $P$.
4. Store one leftover value for every odd frequency group.
5. Try:
   • no leftover, if pair count $\ge 2$;
   • every single leftover $x$ with $x<P$;
   • every adjacent leftover pair $(x,y)$ with $y-x<P$.
6. Output the best perimeter found, or $0$.

Correctness Proof

We prove the algorithm outputs the maximum possible perimeter.

First, consider any valid symmetric polygon. Reflection maps each non-fixed side to a distinct side of equal length. A strictly convex polygon's symmetry axis can fix at most two sides. Therefore, in the selected multiset, all sticks can be grouped into equal-length pairs except for at most two unpaired sticks.

Second, for every length, using as many equal pairs as possible can never hurt. Adding an equal pair increases the perimeter and does not increase the number of unpaired sticks. It also cannot destroy the strict polygon inequality once there is any valid polygon structure, because it adds positive length to the total support against the longest side. Thus some optimal solution uses all possible pairs.

So every optimal solution is exactly: all pairs, plus zero, one, or two odd-frequency leftovers.

Let $P$ be the total length of all paired sticks.

If we add zero leftovers, the paired-only polygon is possible exactly when there are at least two pairs; otherwise there are only two sides. The algorithm checks this candidate.

If we add one leftover $x$, the strict polygon inequality can only fail when $x$ is too long. The paired sticks together have total length $P$, so the necessary and sufficient condition is $x<P$. The algorithm checks every such leftover.

If we add two leftovers $x\le y$, the larger leftover $y$ is the only possible problematic longest side. The strict polygon inequality becomes

$$y < P+x.$$

This is equivalent to $y-x<P$. For each possible larger leftover in sorted order, the best smaller partner is the immediately previous leftover. Therefore checking adjacent pairs finds the maximum valid two-leftover sum.

The algorithm takes the maximum among exactly all possible optimal forms, so it is correct.

Complexity

Sorting dominates:

$$O(n\log n)$$

per test case, with total $n\le 2\cdot 10^5$, so this comfortably passes.