题目描述

小明最近为了锻炼智力，在玩一个数列求和的游戏。设数列的长度为$n$，每一个数字都是整数，且在$[-1000,1000]$范围内，即范围是$-1000到1000$。

游戏规则:小明可以从这个数列里面选一串任意长度的连续子串并求和，小明想知道子串和绝对值的最大值是多少，你能帮帮他吗？

绝对值：正数的绝对值为本身，负数的绝对值为它的相反数。

如$5$ 的绝对值为$5，-7$ 的绝对值为$7$ 。

输入格式

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

输出格式

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

样例数据

输入1

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

输出1

2363

样例1解释

对于样例1，可以发现$232+969+201-111+378-610+127+245+932=2363$ 所以$2363$ 是最大的绝对值。

输入2

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

输出2

2828

样例2解释

对于样例2，可以发现$-838+-958+200+867+-920+-493+114+-800= -2828$ 所以$2828$ 是最大的绝对值。

输入3

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

输出3

1970

数据规模与约定

对于20% 的数据，满足$n<=10$

对于50% 的数据，满足$n<=100$

对于70% 的数据，满足$n<=1000$

对于100% 的数据，满足$n<=1000000$