题目描述

给定一个长度为$n$的序列，求一个子段$[L,R]$，使得$\sum_{i=L}^R a_i$最大，输出这个最大的和。

输入格式

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

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

4
1 -2 3 -4

样例输出 #1

3

说明/提示

对于40%的数据，有$1\leq n\leq 1000$。 对于100%的数据，有$1\leq n\leq 10^5,|a_i|\leq 10^9$。