Balanced Load Split

Hard#dynamic-programming· solved by 0 · time limit 2.0 s

Split $n$ loads (in watts) between two circuits so the difference between the circuits' totals is as small as possible. Print that minimum difference.

Input

$n$ , then $n$ positive integers.

Output

The minimum difference.

Constraints

$1 \le n \le 100$ , $1 \le a_i \le 1000$

Sample 1

Input

4
1 6 11 5

Output

Sample 2

Input

5
3 1 4 2 2

Output