Problem Description

Takahashi and Aoki are playing a game using a sequence $ S $ of length $ N $.

The game consists of one turn each for Takahashi and Aoki.

The game proceeds as follows:

• First, Takahashi marks one element of the sequence.
• Then, Aoki marks one element of the sequence that Takahashi did not mark.
• For the two elements marked by Takahashi and Aoki, all elements between them (inclusive) are kept, and all other elements are removed. The remaining sequence is denoted as $ T $.
• In the sequence $ T $, the sum of the elements at odd positions from the left is Takahashi's score, and the sum of the elements at even positions is Aoki's score.

Aoki will mark the element among those he can choose that allows him to score the most. If there are multiple such elements, he will mark the leftmost one.

Takahashi knows how Aoki will mark his element. Find the maximum score Takahashi can achieve.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ ... $ a_N $

• The first line contains an integer $N\ (2≦N≦50)$, which is the number of elements in sequence $ S $.
• The second line contains $ N $ integers $ a_1 $, $ a_2 $, ... , $a_N\ (-50≦a_i≦50,\ 1≦i≦N)$. The integer $ a_i $ represents the $ i $ -th element of sequence $ S $ from the left.

Output Format

Output the maximum score Takahashi can achieve in one line.

Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

6
1 -3 3 9 1 6

Sample Output #1

6

Sample Input #2

3
5 5 5

Sample Output #2

10

Sample Input #3

8
-1 10 -1 2 -1 10 -1 0

Sample Output #3

-1

Notes/Hints

Sample Explanation 1

Takahashi's best choice is to mark the second element from the left. In this case, Aoki will mark the fifth element, resulting in the sequence $ T $ as $ -3 $, $ 3 $, $ 9 $, $ 1 $. Takahashi scores $ 6 $ and Aoki scores $ 4 $.

Sample Explanation 2

Regardless of which element Aoki chooses, he will always score $ 5 $. Since there are multiple ways to achieve the maximum score, Aoki chooses the leftmost one, allowing Takahashi to score $ 10 $.

见题面 Input 部分

见题面 Output 部分