Last Stone Weight

Each turn, take the two heaviest stones and smash them together. If their weights are equal, both are destroyed; otherwise the lighter one is destroyed and the heavier one is left with the difference of the two weights. Repeat until at most one stone remains, then output the weight of the last stone; output 0 if there are no stones.

The problem rules, examples, and n/weight constraints are complete.

This site adds the standard input/output protocol.

输入格式

The first line contains n (1 ≤ n ≤ 100000), and the second line contains n positive integers weights[i] (1 ≤ weights[i] ≤ 10^9).

输出格式

Output the weight of the last remaining stone; output 0 if all stones are destroyed.

样例 1

输入：

6
1 2 3 6 7 7

输出：

0

样例 2

输入：

1
2

输出：

2

样例 3

输入：

2
5 5

输出：

0