Problem Description

There is a pile of stones represented by an integer array $a$. Each $a_i$ represents the weight of the $i$-th stone.

In each round, any two stones are selected and smashed together. Suppose the weights of the stones are $x$ and $y$, with $x \le y$. The possible outcomes of the smashing are as follows:

• If $x = y$, both stones are completely destroyed;
• If $x \neq y$, the stone with weight $x$ will be completely destroyed, and the stone with weight $y$ will have a new weight of $y - x$.

Eventually, at most one stone will be left. Output the minimum possible weight of this stone. If no stones are left, output $0$.

Input Format

The input consists of two lines.

The first line contains an integer $n$ ($1 \leq n \leq 10000$), representing the number of stones.

The second line contains $n$ integers $a_i$ ($1 \leq a_i \leq 5000$), representing the weight of the $i$-th stone.

Output Format

The output consists of one line.

The first line contains an integer representing the answer.

Sample Input and Output

Sample Input #1

6
2 7 4 1 8 1

Sample Output #1

1

Sample Input #2

5
31 26 33 21 40

Sample Output #2

5

见题面 Input 部分

见题面 Output 部分