Maximize Strength with One Skip

Bobby is taking a walk through a row of mushrooms, where each mushroom has an associated strength value. As he walks, he accumulates the strength values of the mushrooms he admires. However, he is allowed to skip at most one mushroom along his way in order to maximize the total strength he can admire.

Formally, given an integer n and an array of integers a of length n, find the maximum possible sum that can be obtained by selecting a contiguous segment of this array while skipping at most one element. One may think of this as a variation of the maximum subarray problem with one optional skip.

You can interpret the dynamic programming recurrences as follows:

• Let \(dp_{no\_skip}[i]\) be the maximum sum ending at index \(i\) without having used a skip.
• Let \(dp_{skip}[i]\) be the maximum sum ending at index \(i\) with exactly one skip used at some point.

The recurrences are given by:

[ \begin{aligned} dp_{no_skip}[i] &= \max{ dp_{no_skip}[i-1] + a_i,, a_i } \ dp_{skip}[i] &= \max{ dp_{no_skip}[i-1],, dp_{skip}[i-1] + a_i } \end{aligned} ]

The answer is the maximum value among all \(dp_{no\_skip}[i]\) and \(dp_{skip}[i]\) for \(0 \leq i < n\).

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains a single integer n representing the number of mushrooms.
The second line contains n space-separated integers, where each integer represents the strength of a mushroom in the order they appear.

outputFormat

Output a single integer to standard output (stdout) representing the maximum total strength Bobby can admire by walking through the mushrooms while skipping at most one.

## sample

5
1 -2 3 5 -1

9