Problem Description

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

In each round, choose any two stones and smash them together. Suppose their weights are $x$ and $y$, with $x \le y$. Then the possible results are:

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

In the end, at most one stone will remain. Output the minimum possible weight of this stone. If no stone remains, output $0$.

Input Format

The input has 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 has one line.

Output one integer representing the answer.

6
2 7 4 1 8 1

1

5
31 26 33 21 40

5

Hint

Translated by ChatGPT 5