Maximize Ratings

Traverse the movie rating array in its original order and choose a subsequence that maximizes the sum of the chosen ratings. You may not skip two or more movies in a row; skipping a single movie at the start and at the end is allowed. There is no extra requirement to choose at least one movie: when n=1 you may skip the only movie, and an empty selection has a rating sum of 0; when n≥2 you cannot skip all of them.

输入格式

The first line contains n, and the second line contains n integers ratings[i]. Full original ranges: 1≤n≤100000, −1000≤ratings[i]≤1000.

输出格式

Output the maximum rating sum that satisfies the constraint, as an exact integer, with no modulo.

样例 1

输入：

6
-3 2 4 -1 -2 -5

输出：

4

样例 2

输入：

5
9 -1 -3 4 5

输出：

17

样例 3

输入：

1
-1000

输出：

0

样例说明

Original example 1 chooses [2,4,−2] for 4. Original example 2 chooses [9,−1,4,5] for 17, and the original output is kept; the original explanation omitted −1 and wrongly claimed 9+4+5=17 while skipping two movies in a row, which this site explicitly corrects. The original [-1,−3,−2] allows choosing only the second item, which shows that a single skip at the start and at the end is valid; the original has no non-empty requirement, and the third public example, a single −1000→0, is added by this site.