Festival Energy

Every day of the festival has an energy value — positive when the crowd is thriving, negative when it drags. The organisers want to brag about the single best stretch: the contiguous run of days whose total energy is as large as possible.

Find the maximum sum obtainable from one non-empty contiguous segment.

Input

The first line contains one integer n — the number of days.

The second line contains n integers a₁ … aₙ — the daily energy values.

Output

Print the maximum possible energy of one contiguous segment.

Constraints

• 1 ≤ n ≤ 2·10⁴
• −10⁷ ≤ aᵢ ≤ 10⁷
• All days may be negative — the answer is then the single least-bad day.

8
-2 1 -3 4 -1 2 1 -5

6

3
-5 -2 -9

-2