Optimal Task Partition

You are given a set of tasks where each task is associated with a certain number of points. Two participants will solve these tasks and the objective is to distribute the tasks between them such that the absolute difference in their total points is minimized. In other words, you need to partition the set of tasks into two subsets such that the difference in the sum of points between these two subsets is as small as possible.

Formally, given an integer ( n ) and a list of ( n ) integers ( a_1, a_2, \dots, a_n ), find a subset ( S ) such that the absolute difference ( |\sum_{a \in S} a - (\sum_{a=1}^{n} a - \sum_{a \in S} a)| ) is minimized. Output this minimum difference.

Note: The input will be read from standard input and the result must be printed to standard output.

inputFormat

The first line contains an integer ( n ) which denotes the number of tasks. The second line contains ( n ) space-separated integers representing the points for each task.

outputFormat

Output a single integer which is the minimum possible difference between the total points of the two participants.## sample

5
1 2 3 4 5

1