Description

给定一个有n个元素（元素可以为负数）的数字序列，找出其中一个连续子数组，使得它的和最大。

Format

Input

第1行：1个整数n(n≤500000) 
第2行：n个空格分开的整数，每个数的绝对值小于1000.

Output

第1行：1个整数，即满足条件的和。

Samples

5
1 2 3 4 -5

10

Limitation

1s, 1024KiB for each test case.