Maximum Sum with Sliding Window Constraints

Given a sequence \(a_1, a_2, \ldots, a_n\). You are to select zero or more elements from the sequence such that: if you select \(a_i\), then in any contiguous subarray of length \(i\) (formally, any subarray \(a[j, j+i-1]\) for \(1 \le j \le n-i+1\)) you have at most 2 selected elements.

After careful analysis it turns out that any valid selection can contain at most 2 elements. Therefore, the problem reduces to choosing either one element or two elements (or none) such that the sum is maximized.

Your task is to compute the maximum possible sum obtainable under these conditions.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) denoting the number of elements in the sequence.
• The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer — the maximum sum of selected elements under the given constraint.

sample

5
1 2 3 4 5

9