CF33C.Wonderful Randomized Sum

Learn, learn and learn again — Valera has to do this every day. He is studying at mathematical school, where math is the main discipline. The mathematics teacher loves her discipline very much and tries to cultivate this love in children. That's why she always gives her students large and difficult homework. Despite that Valera is one of the best students, he failed to manage with the new homework. That's why he asks for your help. He has the following task. A sequence of n numbers is given. A prefix of a sequence is the part of the sequence (possibly empty), taken from the start of the sequence. A suffix of a sequence is the part of the sequence (possibly empty), taken from the end of the sequence. It is allowed to sequentially make two operations with the sequence. The first operation is to take some prefix of the sequence and multiply all numbers in this prefix by  - 1. The second operation is to take some suffix and multiply all numbers in it by  - 1. The chosen prefix and suffix may intersect. What is the maximum total sum of the sequence that can be obtained by applying the described operations?

学习、学习、再学习——瓦列拉每天都要这样做。他在一所数学学校就读，数学是该校的主修学科。数学老师非常热爱自己的学科，并努力在孩子们心中培养这种热爱。因此，她总是给学生们布置大量且难度很高的作业。尽管瓦列拉是班上最优秀的学生之一，他仍未能完成这次的新作业。因此，他向你求助。他面临如下任务：给定一个包含 $n$ 个数字的序列。序列的一个前缀是指从序列开头起（可能为空）取的一部分；序列的一个后缀是指从序列末尾起（可能为空）取的一部分。允许对序列依次执行两次操作：第一次操作是选取某个前缀，并将该前缀中所有数乘以 $-1$；第二次操作是选取某个后缀，并将该后缀中所有数乘以 $-1$。所选前缀与后缀可以相交。问：通过执行上述操作，所能得到的序列元素总和的最大值是多少？

The first line contains integer n (1 ≤ n ≤ 105) — amount of elements in the sequence. The second line contains n integers a__i ( - 104 ≤ a__i ≤ 104) — the sequence itself.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 序列中元素的个数。
第二行包含 $n$ 个整数 $a_i$（$-10^4 \leq a_i \leq 10^4$）—— 序列本身。

The first and the only line of the output should contain the answer to the problem.

输出的第一行且唯一一行应包含该问题的答案。