A crusher at a quarry is fed a heap of rocks. The list stones holds the weight of each rock. The crusher works in rounds.
In each round it picks the two heaviest rocks and crushes them together. Call their weights a and b, with a <= b.
- If
a == b, both rocks turn to dust.
- If
a != b, the lighter rock turns to dust, and a rock of weight b - a goes back into the heap.
The crusher stops when the heap has at most one rock. Return the weight of the rock that is left, or 0 if the heap is empty.
Examples
Example 1:
Input: stones = [3,9,5]
Output: 1
Explanation: Crush 9 and 5 to get 4, so the heap is [3,4]. Crush 4 and 3 to get 1. The last rock weighs 1.
Example 2:
Input: stones = [6,6]
Output: 0
Explanation: The two rocks weigh the same, so both turn to dust and the heap is empty.
Example 3:
Input: stones = [20]
Output: 20
Explanation: There is only one rock, so the crusher has nothing to do.