问题描述

给定n个整数（可能为负数）组成的序列 $a_1, a_2, a_3,…, a_n$, 求该序列如$a_i+a_{i+1}+...+a_j$的子段和的最大值。

选出的子段不允许为空。

输入

共两行：

第一行一个整数n表示这个序列有n个整数；

第二行 n 个数表示这个序列

输出

一个整数表示这个最大子段和

样例

6
-2 11 -4 13 -5 -2

20

提示

数据范围

$1 \le n \le 10000$

$-1000 \le a_i \le 1000$