题目描述：

给定由n个整数（可能由负整数）组成的序列（a1,a2...an)，求该序列中连续子段和的最大值（至少连续2个数可以组成合格的序列）。

Input

单组数据输入。  第一行:一个正整数n，表示由n个整数。(0<= n <= 100000)  第二行：一共由n个整数ai。整数之间以空格隔开（-10000 <= ai <= 10000)

Output

一个整数，表示最大子段和。

Sample Input

5
-2 -8 5 -4 3

Sample Output

4

Hint

30%的数据,n<=5000;

100%的数据N<=100000;

总和的大小在longint范围之内