Contiguous Sum 2

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.

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$.

Print the largest sum on the first line.