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

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

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

对于 $20\%$ 的数据，满足 $n \leq 10$；
对于 $50\%$ 的数据，满足 $n \leq 100$；
对于 $70\%$ 的数据，满足 $n \leq 1,000$；
对于 $100\%$ 的数据，满足 $n \leq 1,000,000$。

2363

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

2828

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