Minimum Task Time Difference Partition

In this problem, you are given a set of tasks, where each task requires a certain amount of time. Your goal is to partition these tasks between two processors such that the absolute difference between the total processing times of the two processors is minimized.

Formally, if the tasks have durations (a_1, a_2, \dots, a_n) and the total sum is (S = \sum_{i=1}^n a_i), you need to find a subset of tasks whose sum is as close as possible to (\frac{S}{2}). The answer will be (S - 2\times s), where (s) is the maximum sum not exceeding (\frac{S}{2}) that can be formed using a subset of tasks.

This is a classic problem that can be effectively solved using dynamic programming.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) (the number of tasks). The second line contains (n) space-separated integers, each representing the duration of a task.

outputFormat

Output a single integer to standard output (stdout), which is the minimum possible difference between the total time taken by the two processors.## sample

5
2 3 7 1 4

1