Business Magic

There are $n$ stores along a street, numbered from $1$ to $n$ from nearest to farthest. Last month, store $k$ had a net profit of $r_k$. If $r_k$ is positive, it is a profit of $r_k$ dollars. If $r_k$ is negative, it is a loss of $-r_k$ dollars.

You have two kinds of spells that change the net profits for next month.

1. Blue Magic: Choose one continuous interval $[L, R]$. The net profit of every store from $L$ to $R$ (inclusive) is doubled. That is, if $k \in [L, R]$, store $k$ has net profit $2r_k$ next month.
2. Green Magic: Choose any store and cast the spell on it. The store's net profit for next month becomes the negative of its net profit last month.

A store that is not affected by either spell has the same net profit next month as last month.

There are restrictions. You can cast Blue Magic only once, and it must come before Green Magic. Green Magic cannot be cast on any store already affected by Blue Magic. Find the maximum possible total net profit of all stores for next month after casting the spells optimally.

The first line contains $n$, the number of stores. The second line contains $n$ space-separated integers $r_1, r_2, \dots, r_n$, where $r_k$ is the net profit of store $k$ last month.

Output a single integer, the maximum possible total net profit of all stores for next month.

• $1 \le n \le 3 \times 10^5$
• $-10^9 \le r_k \le 10^9$ for $k \in \{1, 2, \dots, n\}$