Minimum Difference Partition

You are given a list of tasks, each with a positive integer duration. Your goal is to partition these tasks into two groups such that the absolute difference between the total durations of the two groups is minimized.

If we denote the total sum of task durations as \(S\) and one subset's sum as \(S_1\), then the answer is \(|S - 2S_1|\). This is a classic dynamic programming problem that can be solved efficiently by determining which subset sums are achievable from the given tasks.

Input and output are provided via standard input and standard output, respectively.

inputFormat

The first line of the input contains an integer \(n\) (the number of tasks). The second line contains \(n\) space-separated integers, where each integer represents the duration of a task.

outputFormat

Output a single integer: the minimum absolute difference between the sums of the two partitions.

## sample

5
10 20 15 5 25

5

</p>