该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，依次表示 $a_1, a_2, \dots, a_n$。

输出格式

输出一行，一个整数，表示朋友们快乐值之和的最大值。

样例输入 1

5
3 2 -1 4 5

样例输出 1

12

样例输入 2

1
10

样例输出 2

10

样例输入 3

6
1 -3 2 10 -4 9

样例输出 3

21

说明

样例解释

• 对于样例 $1$：James 可以邀请第 $1, 4, 5$ 位朋友。
• 对于样例 $2$：James 可以邀请唯一的一位朋友。
• 对于样例 $3$：James 可以邀请第 $3, 4, 6$ 位朋友。

其它样例说明

• 样例 $4$：见选手目录下的 party/party4.in 与 party/party4.ans，该测试用例满足子任务 $2$ 的约束条件。
• 样例 $5$：见选手目录下的 party/party5.in 与 party/party5.ans，该测试用例满足子任务 $3$ 的约束条件。

数据范围

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

各子任务的附加限制如下表所示：

点击下载大样例