题目描述

某人数学老师让他做一道难题。然后他不会，就来请你了。

给你一个数字序列，你可以选择它的某个前缀和后缀（可能是空的）中的每个数字都乘以 $-1$。前缀和后缀可以交叉也可以为空。问能得到的最大序列和是多少。

输入格式

第一行一个整数 $n$，$1\le n\le 10^5$。

第二行 $n$ 个整数 $a_i$，$-10^4\le a_i\le 10^4$。

输出格式

输出一个整数表示答案。

3
-1 -2 -3

6

5
-4 2 0 5 0

11

5
-1 10 -5 10 -2

18