Maximum Flowers Collection

Lila is given a row of n flower beds, where the i^th bed contains a_i flowers. She wants to collect the maximum number of flowers by choosing a contiguous segment of flower beds. However, if the chosen segment contains at least two flower beds, she is required to skip exactly one bed in that segment (i.e. she does not pick the flowers from that one bed).

Formally, for any contiguous segment S of the flower beds:

• If |S| = 1, then the total collected is simply a_i.
• If |S| ≥ 2, then Lila must remove one element from S. That is, if S = [a_i, a_i+1, ..., a_j] with j-i+1 ≥ 2, her collection for that segment is \[ \text{total} = \Bigl(\sum_{k=i}^{j} a_k\Bigr) - \min_{i \le k \le j} (a_k), \] because skipping the smallest element minimizes the loss.

Your task is to determine the maximum number of flowers Lila can collect.

Note: When n = 1, the only possible option is to take the single flower bed.

inputFormat

The input is given from stdin and consists of two lines:

1. The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of flower beds.
2. The second line contains n space-separated positive integers: a₁, a₂, ..., a_n, where each a_i represents the number of flowers in the i^th flower bed.

outputFormat

Output to stdout a single integer — the maximum number of flowers Lila can collect by selecting a contiguous segment and skipping exactly one bed if the segment length is at least 2.

6
3 7 2 5 8 10

33