Description

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

As a master of business magic, you have two types of spells at your disposal that you can use to alter the net profits of these stores for the next month:

1. Blue Magic: You can choose a single continuous interval $[L, R]$. The effect of this spell will be to double the net profit of every store from store $L$ to store $R$ (inclusive) for the next month. That is, if $k \in [L, R]$, then store $k$ will have net profit $2r_k$ next month.

2. Green Magic: You can choose any store and cast the green magic on it. The effect of the green magic is to change the next month’s net profit of that store to the negative of its last month’s net profit.

Any store that has not been affected by either spell will have the same net profit next month as it did last month.

However, there are some restrictions when casting spells. You can only cast the blue magic once and it must be used before the green magic. Additionally, the green magic cannot be cast on any store that has already been affected by the blue magic. Your task is to determine the maximum possible sum of the net profits for all stores for the next month after casting your spells optimally.

Input Format

The first line contains an integer $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 Format

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

5
-2 5 -3 4 -1

20

7
-1 -1 -1 -1 -1 -1 -1

7

4
998244353 864197532 -7 1000000000

5724883756

Hint

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