William is given an array of $N$ integers $a_1,a_2,\dots ,a_n$. He then must pick one contiguous segment $[L,R]$ $(1\le L\le R\le N)$ and multiply all values on that segment $(a_L,\dots ,a_R)$ by $-1$.

His goal is such that after modifying this segment, the sum of the prefix sums is minimized. This value can be represented as:

$${\displaystyle \sum _{i=1}^N\sum _{j=1}^i{a}_j}$$

Output the minimal value attainable under the given terms.

Input Specification

The first line consists of a single integer $N$ $(1\le N\le {10}^5)$.

The next line contains $N$ space-separated integers $a_1,a_2,\dots ,a_N$ $(-1000\le a_i\le 1000)$.

Subtask 1 [20%]

$1\le N\le 2000$

Subtask 2 [80%]

No further constraints.

Output Specification

Output a single integer, the minimal value attainable of the expression outlined above.

Sample Input 1

4
1 -2 100 -5

Sample Output 1

-207

Explanation for Sample 1

If the segment $[3,3]$ was modified our array will become: $[1,-2,-100,-5]$.

The prefix sum of the modified array is:

$[1,-1,-101,-106]$

Thus the answer would be the sum of the prefix sum of all elements:

$\text{ans}=1+(-1)+(-101)+(-106)=-207$

The value $-207$ is the minimum attainable answer.

Sample Input 2

5
-10 7 -2 -2 10

Sample Output 2

-78