P10709 [NOISG 2024 Prelim] Party

Translated from [NOI SG 2024 Prelim B.Party](https://github.com/noisg/noi-2024-prelim)。

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.

The first line contains an integer $n$. The second line contains $n$ integers, representing $a$.

One line with one integer, representing the answer.

### 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 |$\text{Subtask}$|Score|Special Property| |:-:|:-:|:-:| |$0$|$0$|Samples| |$1$|$49$|$n\le 3$| |$2$|$38$|$n\le 1000$| |$3$|$13$|None| 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