HeapSimulation
You have a pile of stones with given weights. Each turn, take the two heaviest stones and smash them together. If they weigh the same both are destroyed; otherwise the lighter one is destroyed and the heavier one is left with weight equal to the difference. Continue until at most one stone is left, and print its weight (0 if none remain).
Input
Line 1: n. Line 2: n stone weights.
Output
Print the weight of the last remaining stone, or 0.
Constraints
1 <= n <= 1000 1 <= weight <= 1000
Example 1
Input
6 2 7 4 1 8 1
Output
1
8 and 7 leave 1, then 4 and 2 leave 2, and so on until a single 1 remains.