Contiguous Sum 2

Interview

Time limit2sMemory limit512 MB

Summary

Find the maximum contiguous subarray sum after optionally deleting at most one element from the sequence.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

You are given a sequence of $n$ integers. Choose one contiguous block of the sequence and add up the numbers in it. Find the largest sum you can get. The block must contain at least one number.

You may remove one number from the sequence. You may also remove nothing. After a removal the remaining numbers close up in order into a new sequence, and the block is chosen from that new sequence.

For example, take the sequence 10, -4, 3, 1, 5, 6, -35, 12, 21, -1. If you remove nothing, the largest sum is 12+21, which is 33. If you remove -35, the sequence becomes 10, -4, 3, 1, 5, 6, 12, 21, -1, and the largest sum is 10-4+3+1+5+6+12+21, which is 54.

Input

The first line contains an integer $n$ ( $1 \le n \le 100000$ ).

The second line contains the $n$ integers of the sequence, separated by spaces. Each number $a_i$ satisfies $-1000 \le a_i \le 1000$ .

Output

Print the largest sum on the first line.

Examples6

Example 1
Input
```
10
10 -4 3 1 5 6 -35 12 21 -1
```
Expected output
```
54
```
Example 2
Input
```
1
-1000
```
Expected output
```
-1000
```
Example 3
Input
```
1
1000
```
Expected output
```
1000
```
Example 4
Input
```
5
-5 -3 -8 -2 -9
```
Expected output
```
-2
```
Example 5
Input
```
7
1 2 3 -100 4 5 6
```
Expected output
```
21
```
Example 6
Input
```
5
1 2 3 4 5
```
Expected output
```
15
```