twomeals

Problem Description

It's Rar's meal time again. This time, he has obtained N delicious (and some not-so-delicious) salmon in a row. The ith salmon from the left has tastiness T_i.

This time, he decides that he is quite full, so he plans to consume it in two seperate meals. For each meal, he can choose a contiguous segment of salmon to eat (possibly none), and his total satisfaction at the end of the day would be the sum of all the salmon he has eaten. Obviously, he cannot eat the same salmon twice.

Help Rar find out what is the maximum satisfaction he can get.

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the array T.

Output

The output should contain one integer, the maximum satisfaction Rar can get.

Limits

|T_i| ≤ 10⁹

Subtask 1 (10%): 1 ≤ N ≤ 50.

Subtask 2 (22%): 1 ≤ N ≤ 300.

Subtask 3 (29%): 1 ≤ N ≤ 2 000.

Subtask 4 (39%): 1 ≤ N ≤ 500 000.

Subtask 5 (0%): Sample Testcases

Sample Testcase 1

Input

6
5 6 -10 4 -1 6

Output

20

Sample Testcase 2

Input

5
2 -1 5 0 -2

Output

7