DMOPC '18 Contest 4 P2 - Dr. Henri and Responsibility

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Python 5.0s
Memory limit: 64M
Python 128M

Author:
Problem type

Dr. Henri is a very busy person. He has responsibilities to attend to over the next two days. Being a very organized person, he wants to split the tasks evenly between the two days. More specifically, if the tasks on day 1 take seconds, and the tasks on day 2 take seconds, he wants to minimize the value of .

The task takes him seconds, and must be completed within a single day. Dr. Henri, being very busy with these tasks, then asks you: what is the minimum value of if he partitions his tasks optimally?

Input Specification

The first line of input will contain an single integer, . The next and final line of input will contain space separated integers:

Output Specification

Output the minimum value of if Dr. Henri partitions the tasks optimally.

Sample Input

6
4 2 3 1 1 1

Sample Output

0

Explanation for Sample Input

If he partitions the task as and , they both sum to , and thus the difference is .