105024 - 求最大子序列和

给一串整数a[1],…,a[n]，求出它的最大的子序列和，即找出1\le i\le j\le n，使得a[i]＋a[i＋1]＋…＋a[j]最大。

Input

输入第一行为一个整数n，表示有n（n\le35 000）个整数，第二行为n个整数。

Output

输出共一行，即最大子序列和。保证输出结果不超过int范围。

Examples

Input

5
1 2 5 -10 7

Output

8

Hint

我们还可以继续进行空间优化，即无需数组，详情请见最新资源包或者参见洛谷P1115题解

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题