Code Submission Evaluation System Login

CSES Problem Set

Apple Division


Task | Statistics


CSES - Apple DivisionCSES - Apple Division

Time limit:1.00 s Memory limit:512 MB

There are $n$ apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Input

The first input line has an integer $n$: the number of apples.

The next line has $n$ integers $p_1,p_2,\dots,p_n$: the weight of each apple.

Output

Print one integer: the minimum difference between the weights of the groups.

Constraints
Example

Input:
5
3 2 7 4 1


Output:
1

Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).