Find Largest Sum Contiguous Subarray

Choose a non-empty contiguous segment of an integer array and output the maximum sum of its elements. Even for an all-negative array, the empty segment may not be chosen.

输入格式

First n is given, followed by n integers. The original gave no numeric bounds; this site publicly adds 1≤n≤200000 and −10^9≤a[i]≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

6
2 -8 3 -2 4 -10

输出：

5

样例 2

输入：

3
-7 -2 -8

输出：

-2

样例 3

输入：

1
0

输出：

0

样例说明

The outputs of the three public examples are, in order: 5; -2; 0. Verified by independent enumeration or direct simulation.