Sequence Sum

Problem Description

Given a sequence $a_0, a_1, \dots, a_{n-1}$ of length $n$, you may reverse one of its contiguous subsegments (possibly empty) so that the sum of the numbers at even indices is maximized.

Input Format

The first line contains an integer $n$, the length of the sequence ($1 \le n \le 2 \times 10^5$).

The second line contains $n$ integers $a_0, a_1, \dots, a_{n-1}$, the sequence $a$ ($1 \le a_i \le 10^9$).

Output Format

Output one integer: the maximum possible sum of elements at even indices.

Sample Input

8
1 7 3 4 7 6 2 9

Sample Output

26