Background

Translated from NOI SG 2024 Prelim B.Party。

Problem Description

James has $n$ friends, and he wants to choose $0$ or more of them to attend his party. If the $i$-th friend attends his party, it will produce $a_i$ points of happiness. Note: some friends do not want to attend the party, so their $a_i$ will be negative.

However, his home only has a single row of $n$ seats, and because of social distancing, two people cannot sit in adjacent seats. Now James wants to know: if he invites friends in the best way, what is the maximum possible sum of happiness values of the invited friends.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, representing $a$.

Output Format

One line with one integer, representing the answer.

5
3 2 -1 4 5

12

1
10

10

6
1 -3 2 10 -4 9

21

Hint

Sample #1 Explanation

James can invite friends $1,4,5$.

Sample #2 Explanation

James can invite the only friend.

Sample #3 Explanation

James can invite friends $3,4,6$.

Constraints

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5,-10^9 \le a_i \le 10^9$.

Translated by ChatGPT 5