题目描述

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，选出其中连续的、非空的一段，使这段中所有数之和最大。请输出这个最大的连续子段和。

输入格式

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

输出格式

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

样例输入 #1

5
2 -1 3 -5 4

样例输出 #1

4

数据范围

$1\le n\le 2\times10^5$，$-10^4\le a_i\le 10^4$。