有一条街上排着 $n$ 家商店，从近到远依次编号为 $1$ 到 $n$。上个月，商店 $k$ 的净利润为 $r_k$。如果 $r_k$ 为正，表示盈利 $r_k$ 元；如果 $r_k$ 为负，表示亏损 $-r_k$ 元。

作为一名商业魔法大师，你可以使用两种魔法来改变这些商店下个月的净利润：

• 蓝色魔法：你可以选择一个单一的连续区间 $[L, R]$。该魔法的效果是将从商店 $L$ 到商店 $R$（含两端）的每家商店下个月的净利润翻倍。也就是说，如果 $k \in [L, R]$，则商店 $k$ 下个月的净利润将变为 $2r_k$。
• 绿色魔法：你可以选择任意一家商店并对其施展绿色魔法。绿色魔法的效果是将该商店下个月的净利润变为其上个月净利润的相反数（即 $-r_k$）。

任何未受到这两种魔法影响的商店，其下个月的净利润将与上个月相同。

然而，施展魔法时存在一些限制。你只能施展一次蓝色魔法，且必须在施展绿色魔法之前使用。此外，绿色魔法不能施展在任何已经被蓝色魔法影响过的商店上。你的任务是确定在最优地施展魔法后，所有商店下个月净利润之和的最大可能值。

输入格式

第一行包含一个整数 $n$，表示商店的数量。

第二行包含 $n$ 个空格分隔的整数 $r_1, r_2, \dots, r_n$，其中 $r_k$ 是商店 $k$ 上个月的净利润。

输出格式

输出一个整数，表示在最优地施展魔法后，所有商店下个月的总净利润的最大可能值。

数据范围

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

样例

输入样例 1

5
-2 5 -3 4 -1

输出样例 1

20

输入样例 2

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

输出样例 2

7

输入样例 3

4
998244353 864197532 -7 1000000000

输出样例 3

5724883756