题目描述

小明最近为了锻炼智力， 在玩一个数列求和的游戏。 设数列的长度为 n， 每一个数字都是整数， 且在[-1000,1000]范围内， 即范围是 -1000~1000。
游戏规则:小明可以从这个数列里面选一串任意长度的连续子串并求和， 小明想知道子串和绝对值的最大值是多少， 你能帮帮他吗？
绝对值：正数的绝对值为本身，负数的绝对值为它的相反数。如 5 的绝对值为 5，-7 的绝对值为 7

输入格式

输入共两行， 第一行为一个整数 n， 第二行为 n 个整数

输出格式

输出一个数， 为数列子串和绝对值的最大值

样例数据1

input

10
-562 232 969 201 -111 378 -610 127 245 932

output

2363

样例数据2

input

10
868 -838 -958 200 867 -920 -493 114 -800 757

output

2828

样例数据3

input

10
-607 -260 -270 -833 560 -280 404 -542 560 -115

output

1970

数据范围

对于 20% 的数据， 满足 n<=10
对于 50% 的数据， 满足 n<=100
对于 70% 的数据， 满足 n<=1000
对于 100% 的数据， 满足 n<=1000000