时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给出一个长度为 \(N\) 的序列 \(A_1、A_2、…、A_N\)，求最大连续和。
　　换句话说，要找到 \(1≤i≤j≤N\)，使得 \(A_i+A_{i+1}+…+A_j\) 尽量大。

【输入格式】

　　第一行一个整数 \(N\)，表示序列的长度。
　　接下来的 \(N\) 行，每行一个整数，第 \(i+1\) 行为 \(A_i\)。

【输出格式】

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

【输入输出样例1】

　Input

7
-2
5
3
-6
4
-8
6

　Output

8

【数据限制】

　　
　　\(30\%\) 的数据有：\(N≤400\)
　　\(60\%\) 的数据有：\(N≤4000\)
　　\(100\%\) 的数据有：\(N≤1000000\) , \(|A_i|≤100000\)

【来源】

　Mr.he