Mr. Kejriwal has got “N” number of cheques, each cheque has Ai amount of money written on it (1 <= i <= N). Now he has to distribute this money for party works in two areas. He has to divide the cheques into two parts such that the difference of sum of money for the two parts is minimum. Can you tell him the minimum difference possible?

Input

The first line will contain "N" the number of cheques. The next line will contain "N" integers Ai (1 <= i <= N) where Ai denotes the amount of money written on the ith cheque.

Output

Output a single integer denoting the minimum difference possible.

Constraints

1 <= N <= 100

0 <= Ai <= 1000

Example

Input:
5
6 5 3 3 8

Output:
1

In the example sets (6, 3, 3) and (5, 8) equals to 12 and 13 respectively, so the minimum possible difference is 1.