给定一个长为 N 的数列 A ，你需要选择一个前缀和一个后缀（可能为空）并将里面所有元素乘以 -1 ，求进行完此操作后数列和的最大值。
第一行一个数表示 N ，第二行 N 个数表示数列。
仅一行一个数表示答案。
3 -1 -2 -3
6
5 -4 2 0 5 0
11
5 -1 10 -5 10 -2
18
1 \leq N \leq 10^5
-10^4 \leq A_i \leq 10^4
对于第 i 个测试点，有 N = 10^{\lceil \frac{i}{2} \rceil} 。
题目来源：Codeforces 33 C