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~ ~(-1\,000 \le a_i \le 1\,000)~.

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