题目描述

有n个整数排成一排。例如n=7时，对应的数为-2 13 12 9 14 -10 2，其最大的部分和为 48（即 13+12+9+14）。 求这n个整数的最大连续部分和。

输入格式

第一行一个整数 n 第二行n个整数，数之间有一个空格；保证其中有正数。

输出格式

输出一个整数，即这n个整数的最大连续部分和。

样例输入

7
-2 13 12 9 14 -10 2

样例输出

48

数据范围与提示

对于 60% 的数据，$1 \le n \le 10^4$； 对于 100% 的数据，$1 \le n \le 10^6$，$-100 \le x_i \le 100$。