You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 NOI SG 2024 Prelim B.Party。

题目描述

James 有 $n$ 个朋友，他想选择其中的 $0$ 个或者更多朋友来参加他的聚会。第 $i$ 个朋友如果参加了他的聚会，会产生 $a_i$ 点快乐值。注意：有些朋友并不想参加聚会，所以他们的 $a_i$ 会是负的。

然而，他家只有一排 $n$ 个座位，而且因为社交距离，两个人不能坐在相邻的座位上。现在 James 想知道，如果他按照最优方案邀请朋友，这些朋友的快乐值的和最大为多少。

输入格式

第一行，一个整数 $n$。

第二行 $n$ 个整数，表示 $a$。

输出格式

一行一个整数，表示答案。

5
3 2 -1 4 5

12

1
10

10

6
1 -3 2 10 -4 9

21

提示

【样例 #1 解释】

James 可以邀请第 $1,4,5$ 位朋友。

【样例 #2 解释】

James 可以邀请唯一一位朋友。

【样例 #3 解释】

James 可以邀请第 $3,4,6$ 位朋友。

【数据范围】

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5,-10^9 \le a_i \le 10^9$。