Một ông bố có n tài sản có giá trị lần lượt là a1,a2,…,an. Ông chỉ có hai người con ông muốn đem chia n tài sản này cho 2 người con sao cho chênh lệch giữa 2 người là ít nhất có thể.

Input

Dòng thứ nhất số nguyên dương n là tài sản ( 1 ≤ n ≤ 20)

Dòng thứ hai chứa n số nguyên dương có giá trị tuyệt đối không quá 10^4

Output

Một số nguyên là độ chênh ít nhất có thể của hai người con

Example 1

Input

3
8 4 6

Output

2

Giải thích: Một người nhận 8 một người nhận 4+6=10 nên chênh lệch ít nhất 2

Example 2

Input

5
10 7 9 6 6

Output

0

Giải thích: Một người nhận 10+9 =19 một người nhận 7+6+6=19 nên chênh lệch ít nhất 0