说明(数据已经加强)

有 $n$ 个整数（$1≤n≤10^6$），排成一排，例如： $n=7$

$-2\ 13\ 12\ 9\ 14\ -10\ 2\ （7个整数）$

其最大的部分和为 $48 （即 13+12+9+14）$

输入格式

第一行一个整数 $n$

第二行n个整数（$-10^6≤x_i≤10^6$）

数之间有一个空格；其中 $x_i$ 有正数

输出格式

一个整数（即最大的连续的部分和）

样例

7
-2 13 12 9 14 -10 2 

48