Arrangement

Problem Description

Teacher Komila Sobirovna has $n$ desks in the class, arranged in a row. When a student sits at desk $i$, the teacher's pleasure changes by $p[i]$.

There are exactly $\lceil \frac{n}{2} \rceil$ students in the class. Komila Sobirovna needs to seat all students at desks such that no two students sit at neighboring desks. Among all valid arrangements, find the one that maximizes the total pleasure.

Note: $\lceil x \rceil$ denotes the smallest integer greater than or equal to $x$. For example, $\lceil 3.14 \rceil = 4$ and $\lceil 5 \rceil = 5$.

Input Format

The first line contains an integer $n$ --- the number of desks.

The second line contains $n$ integers $p[1], p[2], \ldots, p[n]$ --- the impact of each desk on the teacher's pleasure.

Constraints:

$1 \leq n \leq 10^5$

$-10^9 \leq p[i] \leq 10^9$, for each $1 \leq i \leq n$

Output Format

On a single line, print the maximum pleasure the teacher can get.

Scoring

Notes

In the first sample, $n=6$ and $\lceil \frac{6}{2} \rceil = 3$ students. Komila Sobirovna seats them at desks $1$, $4$, and . Total pleasure: .

In the second sample, $n=3$ and $\lceil \frac{3}{2} \rceil = 2$ students. The only option is desks $1$ and $3$. Total pleasure: .

6
5 2 -1 3 -4 7

15

3
-1 -2 -3

-4