# 2128. Maximum subsequence sum

Let a_1, a_2, …, a_n be a sequence of integers. A contiguous subsequence of this sequence is a subsequence a_i, a_i+1, …, a_j-1, a_j for some i,j such that 1 <= i <= j. You have to write a program which when given a sequence of integers, outputs the maximum possible sum of any contiguous subsequence of the sequence.

### 输入格式

First line of the input will be n, the number of integers in the subsequence. n can be as large as upto 100,000. This will be followed by n integers. Each integer will appear on a different line, and there will be no blank lines in the input.

### 输出格式

Output the maximum possible sum as defined above.

### 样例

Input
10
-1
-2
3
-1
4
2
-6
7
-1
5

Output
13


39 人解决，82 人已尝试。

47 份提交通过，共有 108 份提交。

5.0 EMB 奖励。