#### Registered Users Only

Please login to view and utilize this feature.

## 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 *i*th 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^{9}

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 22 | 1s | 256MB | Minimum |

2 | 22 | 42 | 1s | 256MB | Minimum |

3 | 29 | 62 | 1s | 256MB | Minimum |

4 | 39 | 82 | 1s | 256MB | Minimum |

5 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o twomeals -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512