You are given a list of ~N~ items. Each item has a value ~a_i~ (~a_1~, ~a_2~,..., ~a_n~). Let's split these items into two subsets such that the absolute difference between their sums is minimum. Calculate this difference.

Input

• The first line contains an integer ~N~ (~1 \leq N \leq 100~).
• The second line has ~N~ integers ~a_1~, ~a_2~..., ~a_n~ respectively (~0 \leq a_i \leq 10^7~ and ~0 \leq a_1+a_2+…+a_n \leq 10^7~).

Output

• Print minimum difference between two sets.

Example Input 1

7
1 2 3 4 5 6 7

Example Output 1

0

Example Input 2

4
1 11 5 6

Example Output 2

1