Maximum Subarray Sum with Skips

Kotlin Hard lists

Task «Maximum Subarray Sum with Skips»

Given a list of integers. It is necessary to find the maximum sum of a subarray (continuous sequence of elements), provided that no more than one element can be removed from this subarray (to obtain a larger sum). Removing an element is optional. If the list is empty, the sum is considered to be 0. The length of the list is up to 10^5, elements range from -10^4 to 10^4.

Input Format

The first line contains an integer N (1 ≤ N ≤ 100000) — the number of elements in the list. The second line contains N integers separated by spaces.

Output Format

One integer — the maximum possible sum of a subarray after removing at most one element.

Examples

Example 1

INPUT

3
10 20 30

OUTPUT

60

Example 2

INPUT

1 2 3

OUTPUT

2

main.kt