867. Joining the Ropes
You have n ropes of given lengths. Joining two ropes costs the sum of
their lengths and produces one rope of that length. Print the least total cost
to join them all into one. With a single rope the cost is 0.
Always join the two SHORTEST ropes available. The reason is that every join a rope takes part in adds its length to the total again, so a short rope should be joined early and a long one late.
This is the shape a heap exists for. The result of each join goes back in and competes with the originals, so the set of candidates keeps changing. Sorting once is not enough: the rope produced by the first join may be shorter than ropes still waiting, and must be considered against them.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ length ≤ 100000`
Input
The first line contains an integer n.
The second line contains n space-separated rope lengths.
Output
Print one integer: the least total cost to join every rope into one.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.