666. Pairing Players Into Teams of Equal Skill

An even number of players is given, each with a skill rating. Pair them into teams of two so that EVERY team has the same total skill.

If that is possible, print the sum over teams of the PRODUCT of the two skills. If it is impossible, print -1.

3 2 5 1 3 4 -> 22 teams (1,5) (2,4) (3,3), products 5 + 8 + 9 3 4 -> 12 the only team 1 2 3 4 -> -1

## The target total is forced

If a valid pairing exists, the smallest player must be with somebody, and so must the largest. They must be with EACH OTHER: if the smallest were paired with anyone else, that team's total would be below the largest player's team total, because the largest is in some team whose total is at least its own value.

So the required total is min + max, and it is determined before any choice is made.

## Sort and pair the ends inward

sort i = 0, j = n-1, target = a[0] + a[n-1] while i < j: if a[i] + a[j] != target: answer -1 total += a[i] * a[j] i += 1; j -= 1

Once the outermost pair is fixed, the same argument applies to what remains, so the pairing peels inward with no choices left anywhere.

## Why any mismatch is fatal

There is exactly one candidate pairing, so a single pair missing the target means no valid pairing exists at all. There is nothing to backtrack over, which is what makes this linear rather than a search.

## The products are not the hard part

The chemistry total is just carried along. It is there to make the answer depend on WHICH pairing was formed rather than only on whether one exists, so a solution cannot pass by checking feasibility alone.

## Overflow

Two skills near 1000 give a product near 10^6, and 100000 teams give a total near 10^11. The total needs 64 bits.

## Boundaries

Two players always succeed, whatever their skills. All players equal succeed, and the total is n/2 copies of that value squared.

## Cost

Time O(n log n) for the sort. Space O(1) beyond the input.

Constraints - `2 ≤ n ≤ 200000` and `n` is even - `1 ≤ each skill ≤ 1000`