题目背景
翻译自 [NOI SG 2024 Prelim B.Party](https://github.com/noisg/noi-2024-prelim)。
题目描述
James 有 $n$ 个朋友，他想选择其中的 $0$ 个或者更多朋友来参加他的聚会。第 $i$ 个朋友如果参加了他的聚会，会产生 $a_i$ 点快乐值。注意：有些朋友并不想参加聚会，所以他们的 $a_i$ 会是负的。 然而，他家只有一排 $n$ 个座位，而且因为社交距离，两个人不能坐在相邻的座位上。现在 James 想知道，如果他按照最优方案邀请朋友，这些朋友的快乐值的和最大为多少。
输入格式
第一行，一个整数 $n$。 第二行 $n$ 个整数，表示 $a$。
输出格式
一行一个整数，表示答案。
说明/提示
### 【样例 #1 解释】 James 可以邀请第 $1,4,5$ 位朋友。 ### 【样例 #2 解释】 James 可以邀请唯一一位朋友。 ### 【样例 #3 解释】 James 可以邀请第 $3,4,6$ 位朋友。 ### 【数据范围】 |$text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$0$|$0$|样例| |$1$|$49$|$nle 3$| |$2$|$38$|$nle 1000$| |$3$|$13$|无| 对于 $100%$ 的数据，$1 le n le 2 times 10^5,-10^9 le a_i le 10^9$。
