Dr. Henri is a very busy person. He has ~N~ 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 ~t_1~ seconds, and the tasks on day 2 take ~t_2~ seconds, he wants to minimize the value of ~|t_1 - t_2|~.

The ~i^\text{th}~ task takes him ~A_i~ 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 ~|t_1 - t_2|~ if he partitions his tasks optimally?

Constraints

~0 \le A_i \le 700~

Subtask 1 [20%]

~1 \le N \le 20~

Subtask 2 [80%]

~1 \le N \le 700~

Input Specification

The first line of input will contain a single integer, ~N~.
The next and final line of input will contain ~N~ space separated integers: ~A_1, A_2, \dots, A_N~.

Output Specification

Output the minimum value of ~|t_1 - t_2|~ if Dr. Henri partitions the tasks optimally.

Sample Input

6
4 2 3 1 1 1

Sample Output

0

Explanation for Sample Output

If he partitions the task as ~\{2, 3, 1\}~ and ~\{4, 1, 1\}~, they both sum to ~6~, and thus the difference is ~0~.