P15906 [TOPC 2024] Business Magic

沿街有 $n$ 家商店，按从近到远的顺序编号为 $1$ 到 $n$。上个月，商店 $k$ 的净利润为 $r_k$。如果 $r_k$ 为正，表示盈利 $r_k$ 美元；如果 $r_k$ 为负，表示亏损 $-r_k$ 美元。 作为一名商业魔法大师，你拥有两种魔法，可以用来改变这些商店下个月的净利润： 1. **蓝魔法**：你可以选择一个连续的区间 $[L, R]$。该魔法的效果是将从商店 $L$ 到商店 $R$（包含两端）的每家商店的净利润翻倍。也就是说，如果 $k \in [L, R]$，那么商店 $k$ 下个月的净利润为 $2r_k$。 2. **绿魔法**：你可以选择任意一家商店对其施放绿魔法。绿魔法的效果是将该商店下个月的净利润变为上个月净利润的相反数。 任何未受任何魔法影响的商店，其下个月的净利润与上个月相同。 然而，施放魔法时有一些限制。你只能施放一次蓝魔法，且必须在绿魔法之前施放。此外，绿魔法不能施放在任何已经受到蓝魔法影响的商店上。你的任务是确定在最优施放魔法后，所有商店 **下个月净利润总和的最大可能值**。

第一行包含一个整数 $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\}$ 翻译由 DeepSeek V3.2 完成