The greatest sum

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

There is a sequence A1, A2, ..., AN. You can only select a successive part. Then what is the greatest sum of the select part.

Input

Line 1: A integer N (1 ≤ N ≤ 10^6)), the length of sequence Line 2: N integers A1, A2, ..., AN (-100<=Ai<=100), the sequence.

Output

An integer, the greatest sum.

Sample Input

10
-1 8 -1 8 -3 2 -4 4 -7 6

Sample Output

15

Hint

Source

NJUSTACMCONTEST--WAVwind

提交代码