题目描述

给一个长度为 $n$ 的整数序列 $a$，选出其中连续且非空的一段使这段的和最大。

输入格式

第一行一个整数 $n$ ，表示数列的长度；

第二行 $n$ 个整数，表示数列 $a_i$。

输出格式

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

样例1

输入

7
2 3 4 -5 6 -1 2

输出

11

数据规模与约定

对于 $50\%$ 的数据，保证 $n\le 5000$；

对于 $100\%$ 的数据，保证 $n\le 2\times 10^5,\left| a_i\right| \le 10^9$。