题目描述

给出一个整数数列 $a_{1}$,$a_{2}$,⋯,$a_n$，这个数列可能包含负数。

一个机器人初始在数轴的坐标 0 点，按照以下流程移动：

向正方向移动 $a_{1}$ 单位长度。

向正方向移动 $a_{1}$ 单位长度，再向正方向移动 $a_{2}$ 单位长度。

⋮

向正方向移动 $a_{1}$ 单位长度，再向正方向移动 $a_{2}$ 单位长度，……，最后向正方向移动 $a_n$ 单位长度。

因为数列中包含负数，所以当 $a_i\lt 0$ 时，“向正方向移动 $a_i$ 单位长度”会让机器人向负方向移动 $|a_i|$ 单位长度。

你需要求出机器人在整个移动过程中，坐标的最大值。

输入格式

第1行，1个整数n

第2行，n个正整数$a_{1}$,$a_{2}$,⋯,$a_n$

输出格式

输出机器人在整个移动过程中，坐标的最大值。

样例输入

3
2 -1 -2

样例输出

5

提示

机器人移动过程如下：

向正向移动 2，停在坐标 2。

向正向移动 2，停在坐标 4。再向正向移动 −1，这相当于向负方向移动 1，停在坐标 3。

向正向移动 2，停在坐标 5。再向正向移动 −1，停在坐标 4。最后向正向移动 −2，停在坐标 2。

整个移动过程中，最大的坐标是 5。

数据范围

$1\le n\le 2\times 10^{5}$

$-10^{8}\le a_i\le 10^{8}$

3
2 -1 -2

5

3 
2 -1 -2

5

1
-100000000

0