#241EasyHeaps· Repeated Extraction of the Two Largest

Last Surviving Crate

A recycling plant crushes crates with a hydraulic press. Each crate has a positive integer weight. The operator repeats the same step until at most one crate is left: 1. Pick the **two heaviest** crates and press them together. 2. If both crates weigh the same, they are both destroyed. 3. Otherwise the lighter crate is destroyed and the heavier one stays on the belt, now weighing the **difference** of the two weights. Return the weight of the last crate on the belt, or `0` if no crate is left.

Input format

`weights`: an array of positive integers, the crate weights.

Output format

A single integer: the weight of the last crate, or 0 when all crates were destroyed.

Examples

Input: weights = [2, 7, 4, 1, 8, 1]

Output: 1

Press 8 and 7 to get 1. Now 2, 4, 1, 1, 1: press 4 and 2 to get 2. Now 2, 1, 1, 1: press 2 and 1 to get 1. Now 1, 1, 1: press two of them, both vanish. One crate of weight 1 remains.

Input: weights = [5, 5]

Output: 0

Two equal crates destroy each other, so nothing is left and the answer is 0.

Input: weights = [9]

Output: 9

A single crate is never pressed; its weight 9 is the answer.

Constraints

1 <= weights.length <= 10^5
1 <= weights[i] <= 10^4

#heap
#priority-queue
#simulation
#greedy