Problem Statement

There are $N$ integers arranged in a row from left to right on a table. You will now perform the following operation any number of times, possibly $0$ times.

• Choose integers $l,r\ (1 \le l \le r \le N)$. Replace all of the $l,l+1,\dots,r$-th integers from the left on the table with their maximum value.

Find the maximum possible value of the sum of the absolute values of the integers after the operations.

Input

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Line $1$ gives $N$, the number of integers arranged on the table. $N$ satisfies $1 \le N \le 200000$.

Line $2$ gives the $N$ integers $A_1,A_2,\dots,A_N$ arranged on the table, separated by single spaces. Each $A_i$ satisfies $-1000000000 \le A_i \le 1000000000$.

Output

Output the answer, followed by a newline.

Sample

4
2 -2 1 -3

9