机器人的移动

题目描述

给定数列 $A_1, A_2, A_3, \dots, A_N$。这个数列可能包含负数元素。

放在数轴坐标 $0$ 处的机器人依次执行以下动作：

• 向正方向前进 $A_1$。

• 先向正方向前进 $A_1$，再向正方向前进 $A_2$。

• 先向正方向前进 $A_1$，再向正方向前进 $A_2$，再向正方向前进 $A_3$。

$\hspace{140pt} \vdots$

• 依次向正方向前进 $A_1$、$A_2$、$A_3$、$\dots$、$A_N$。

请计算从动作开始到结束为止，机器人坐标的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

输出从动作开始到结束为止机器人坐标的最大值。

样例

3
2 -1 -2

5

机器人按如下方式移动：

• 向正方向前进 $2$，坐标变为 $2$。

• 向正方向前进 $2$，坐标变为 $4$。接着向正方向前进 $-1$，坐标变为 $3$。

• 向正方向前进 $2$，坐标变为 $5$。接着向正方向前进 $-1$，坐标变为 $4$。再向正方向前进 $-2$，坐标变为 $2$。

动作中坐标的最大值为 $5$，所以输出 $5$。

5
-2 1 3 -1 -1

2

5
-1000 -1000 -1000 -1000 -1000

0

这种情况下，最初所在的坐标 $0$ 是最大值。

数据范围

• $1 \le N \le 200000$
• $-10^8 \le A_i \le 10^8$
• 输入均为整数