题目描述

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

游戏规则：小明可以从这个数列里面选一串任意长度的连续子串并求和，小明想知道子串和绝对值的最大值是多少，你能帮帮他吗？ 绝对值：正数的绝对值为本身，负数的绝对值为它的相反数。 如 $5$ 的绝对值为 $5$，$-7$ 的绝对值为 $7$ 。

输入格式

从文件 sequence.in 中读入数据。

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

输出格式

输出到文件 sequence.out 中。

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

样例

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

2363

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

2828

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

1970