题目描述

给定 $n$ 个整数排成一排。求这些整数的最大连续子段和（即连续若干个数之和的最大值）。

例如 $n=7$，数列为 $-2,13,12,9,14,-10,2$，其最大连续子段和为 $48$（$13+12+9+14$）。

输入格式

第一行一个整数 $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$。