Maximum subarray sum with one element deletion

Java Hard arrays

Task «Maximum subarray sum with one element deletion»

Given an integer array. It is necessary to find the maximum sum of a subarray (continuous sequence of elements) provided that you can remove at most one element (or not remove any). The subarray must contain at least one element. It is required to implement an algorithm with a time complexity of O(n) and constant extra memory.

Input Format

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of elements in the array. The second line contains n integers separated by spaces — the elements of the array (their absolute values do not exceed 10^4).

Output Format

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

Examples

Example 1

INPUT

5 1
1 2 3 2 4

OUTPUT

9

Example 2

INPUT

2
7 1
-4 3

OUTPUT

8

Example 3

INPUT

6
2 -1 2 3 4 -5

OUTPUT

11

main.java