Minimum Subset Sum Difference

Problem Statement:

You are given a list of non-negative integers. Your task is to partition this list into two groups such that the absolute difference between the sums of the two groups is minimized. Formally, if the two groups have sums S₁ and S₂ respectively, you need to minimize |S₁ - S₂|. This can be expressed in LaTeX as: $$\min \left| \sum_{i \in Group1} a_i - \sum_{j \in Group2} a_j \right|$$.

For example, given the list [1, 2, 3, 4, 5], one possible partition yields an absolute difference of 1. Your goal is to compute this minimum difference for any given list.

inputFormat

Input Format:

The first line contains an integer n, representing the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Output Format:

Output a single integer denoting the minimum possible absolute difference between the sums of the two groups.## sample

5
1 2 3 4 5

1