D. Median Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \ldots, a_n$$$ consisting of $$$n$$$ integers.

Let's define $$$p$$$, $$$q$$$ and $$$x$$$ as follows:

  • $$$p$$$ is the minimum possible sum of a subsequence of $$$a$$$.
  • $$$q$$$ is the maximum possible sum of a subsequence of $$$a$$$.
  • $$$x$$$ is the sum of any arbitrary subsequence, $$$s$$$, of $$$a$$$.
Your target is to choose an arbitrary subsequence, $$$s$$$, of $$$a$$$ for which $$$|2\cdot x - (p + q)|$$$ is minimum possible.

Print the minimum possible value of $$$|2\cdot x - (p + q)|$$$.

Subsequence of an array can be obtained by erasing some (possibly zero or all) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array $$$[5,3,1,2,4]$$$ the following arrays are subsequences: $$$[3], [5,3,1,2,4], [5,1,4]$$$, but the array $$$[1,3]$$$ is not.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ $$$(-500 \le a_i \le 500)$$$ — elements of the array $$$a$$$.

Output

Print the minimum possible value of $$$|2\cdot x - (p + q)|$$$.

Examples
Input
3
3 -2 4
Output
1
Input
2
1 2
Output
1
Note

In the first case, $$$p=-2$$$ and $$$q=7$$$. Let $$$s = [-2, 4]$$$ then $$$x=-2+4=2$$$ and $$$|2\cdot x-(p+q)|=1$$$. And, this is the minimum possible answer.