Minimum Task Time Difference

You are given a list of task durations. Your goal is to divide these tasks between two workers (Worker A and Worker B) such that the absolute difference in their total working times is minimized.

Let the durations be a list of integers \(d_1, d_2, \ldots, d_n\). If Worker A takes a subset of tasks with a total duration of \(S_1\) and Worker B takes the rest with a total duration of \(S_2\), then the objective is to minimize:

\( |S_1 - S_2| \)

This is equivalent to partitioning the set into two subsets with the minimum possible difference between the sums. A common approach to solve this problem is to use dynamic programming to determine the largest sum that does not exceed \(\frac{\text{total sum}}{2}\) and then compute the difference.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a single integer \(n\) — the number of tasks.
2. The second line contains \(n\) space-separated positive integers representing the duration of each task.

outputFormat

Output a single integer to stdout — the minimum possible difference between the total working time of the two workers.

## sample

5
1 2 3 4 5

1

</p>