Codeforces Round 929 Div.3 A-E

A. Turtle Puzzle: Rearrange and Negate

每个测试的时间限制为2秒；每个测试的内存限制为256兆字节；输入：标准输入；输出：标准输出

This task provides you with an array a, consisting of n integer values. It is required that you carry out these two operations in sequence: first, [operation one], and second, [operation two].

1. 重新排列数组中的元素或使其元素顺序保持不变。
2. 选择一个连续的一段元素并翻转该段所有元素的符号。正式地来说，在满足1 ≤ l ≤ r ≤ n的情况下可以选择一对索引l, r并将所有满足l ≤ i ≤ r的a_i设置为其相反数（翻转符号）。注意可以选择不选择任何这样的区间而使所有元素的符号保持不变。

What is referred to as the maximum value of the array items after performing these two operations (first and then)?

Input

The top line of the i