Challenge: Smash the Stones

Lab Python Intermediate 20 points

You have stones with weights. Each turn, take the two heaviest stones and smash them: if they're equal both are destroyed; otherwise the lighter one is destroyed and the heavier one's weight becomes the difference. Print the weight of the last stone left, or 0 if none are left. Use a max-heap.

Input

One line of positive whole numbers.

Output

One number.

Example

Input

2 7 4 1 8 1

Output

Sample input available Sample output available

Editor

Python

Hints

heapq is a min-heap: store negative weights to get the heaviest first.

Push back the difference if it isn't 0.

Solution explanation

Each turn is O(log n), and there are at most n turns.

Show solution

import heapq
heap = [-int(x) for x in input().split()]
heapq.heapify(heap)
while len(heap) > 1:
    a = -heapq.heappop(heap)
    b = -heapq.heappop(heap)
    if a != b:
        heapq.heappush(heap, -(a - b))
print(-heap[0] if heap else 0)

Output

Answer