学习、学习、再学习——Valera 每天都必须这样做。他正在数学学校学习,数学是该校的主要学科。这位数学老师非常热爱她的学科,并努力培养孩子们的这种热爱。这就是为什么她总是给学生布置大量且困难的作业。尽管瓦莱拉是最好的学生之一,但他未能完成新作业。这就是他请求你帮助的原因。他有以下任务。给出一个由 n 个数字组成的序列。序列的前缀是序列的一部分(可能为空),从序列的开头获取。序列的后缀是序列的一部分(可能为空),取自序列的末尾。允许顺序地对序列进行两次操作。第一个操作是取序列的某个前缀,并将该前缀中的所有数字乘以 - 1。第二个操作是取某个后缀,并将其中的所有数字乘以 - 1。所选的前缀和后缀可能会相交。通过应用所描述的操作可以获得的序列的最大总和是多少?
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 序列中的元素数量。第二行包含 n 个整数 ai ( - 104 ≤ ai ≤ 104) — 序列本身。
输出
输出的第一行也是唯一一行应包含问题的答案。
示例
输入 #1
3 -1 -2 -3
输出 #1
6
输入 #2
5 -4 2 0 5 0
输出 #2
11
输入 #3
5 -1 10 -5 10 -2
输出 #3
18