Last Stone Weight

You have a collection of stones. Repeatedly pick the two heaviest stones and smash them together: if they're equal, both are destroyed; if not, the lighter one is destroyed and the heavier one's weight becomes the difference. Print the weight of the last remaining stone, or 0 if none remain.

Example

Input: 2 7 4 1 8 1 Output: 1

Approach

"Always pick the two heaviest" is exactly what a max-heap is for. Python's heapq is a min-heap, so a common trick is to push negated values to simulate a max-heap. Pop the two largest, push back the difference (if any), and repeat until at most one stone remains.

Input format

Line 1: the stones, space-separated

Print the final weight.