题目背景

小明对手工很感兴趣，立志成为一名工匠。他一到暑假就会到自家开的工厂里帮工人师傅打下手，学习一些身为工匠应具备的技能。

题目描述

有一条由 $n$ 个钢圈组成的钢条，将钢圈按 $1\sim n$ 编号。其中一些钢圈有损坏，小明依次测量了每个钢圈的健康度，健康度为正数的是没有损坏的钢圈，为负数的说明有损坏且数字越小损坏程度越严重。

现在小明要用手头上已有的工具和材料对钢条进行修复，但是受限于修复的技术，小明只能修复连续的一整段钢圈，这段钢圈的起点 $begin$ 和终点 $end$ 可以任意选择（必须至少对一节钢圈进行修复）。经过修复后，这些钢圈的健康度会变为相反数，也就是负数变正数，正数变负数。

为了使得修复的效果尽可能好，小明需要使得修复后整段钢条的总健康度最大。请你帮小明计算一下修复后整段钢条的总健康度最大是多少？

输入格式

第一行一个整数 $n$，表示钢圈数量

第二行 $n$ 个整数 $a_i$，对应每个钢圈的健康度

输出格式

一个整数，符合题目要求的答案

样例数据

6
-1 7 -4 -2 5 -8

15

样例解释

样例一中，小明选择修复 $[3,6]$ 这段钢圈，修复后整体健康度变为 -1 7 4 2 -5 8，此时总健康度为 $15$。是所有修复方案中最优的。

数据范围

对于 $10\%$ 的数据，$1 \le a_i \le 1000$

对于 $50\%$ 的数据，$1 \le n \le 100$

对于 $100\%$ 的数据，$1 \le n \le 2000, -1000 \le a_i \le 1000$