A foundry has n ingots with given positive integer masses. Repeatedly, while at least two ingots remain, take the two heaviest ingots with masses a >= b and smash them: if a == b both are destroyed; otherwise both are removed and a new ingot of mass a - b is produced. (Ties among the heaviest are interchangeable and do not affect the result.)
When at most one ingot remains, report its mass, or 0 if none remain.
Input format
Line 1: an integer n.
Line 2: n space-separated positive integers, the ingot masses.
Output format
A single integer: the final remaining mass, or 0 if no ingot remains.
Constraints
- 1 <= n <= 100000
- 1 <= each mass <= 1000000