题目描述

现给定一串数N，求出连续的数相加的最大值，例如：1 6 9 -5 4，连续数的最大和就是1+6+9=16；6 -3 4 0。

输入格式

第一行一个整数 n，第二行 n 个整数（1 ≤ n ≤ 10000）

输出格式

输出一行一个整数

样例

输入 # 1

5

1 6 9 -5 4

5

6 -3 4 0 -1

输出 # 1

16

7