题目内容

你有一个包含整数的数组 a，数组中的每个元素可以是正数、负数或零。

现在，你拥有一种特殊的能力：

• 你可以选择数组中的任意一段连续的子数组，并将这段子数组内的每个数字都变成其相反数。这个操作可以执行0次或1次。

你的任务是，利用这个特殊能力，找出在执行操作后能够达到的最大和的连续子数组。这里所指的“最大和”是指经过可能的变换操作后，任意连续子数组元素之和的最大值。需要注意的是，最终选择的子数组至少应包含一个元素。注意：取反的子数组跟最终求和的子数组并不需要相同。

输入描述

• 第一行包含一个整数 n (2 <= n <=10^5))，表示数组中数字的个数。
• 第二行包含 n个整数，依次为 a_1, a_2, ..., a_n (-10^4 <= a <= 10^4)

输出描述

输出一个整数，表示在执行操作后能够达到的最大和的连续子数组之和。

样例1

输入

6
3 1 -6 2 -5 3

输出

16

说明

首先选择 [-6, 2, -5] 进行变换，原数组变为 [3, 1, 6, -2, 5, 3]，此时选择整个数组序列，可得最大总和为16。

样例2

输入

7
-1 -1 8 -9 7 -1 -1

输出

24

说明

首先选择子数组 [-9]进行变换，原数组变为 [-1, -1, 8, 9, 7, -1, -1]，此时选择 [8, 9, 7]子数组，可得最大总和为24。

样例3

输入

5
1 3 4 2 5

输出

15

说明

首先不进行任何变换，然后此时选择整个数组序列，可得最大总和为15。