题目描述

设数组$\red{a}$是有$\red{n}$个元素的整数数组，从中找出最大和子序列。

最大和子序列：数组中连续元素（子序列）相加和的最大值。

数组：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，

最大和子序列为$\red{16}$，最大子序列为：5 3 2 -1 6 -9 10

输入格式

第一行一个整数$\red{n}$，$\red{n<=1000}$；

第二行，$\red{n}$个绝对值不大于$\red{10000}$的整数。

输出格式

一个整数，子序列和中最大值。

样例

输入数据

12
-6 2 4 -7 5 3 2 -1 6 -9 10 -2

输出数据

16