题目描述

现给出一个长度为 $n$ 的整数数组，找出其中一段连续的元素，使其的和最大。

格式

输入

第一行，一个整数 $n$。 第二行，$n$个整数 $a_i$。

输出

一个整数，即最大的连续和。

样例

9
-2 1 -3 4 -1 2 1 -5 4

6

提示

数据范围

• $1 \leq n \leq 10^5$
• $-10^4 \leq a_i \leq 10^4$