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

题目描述

小帅 拥有 $n$ 位朋友，并计划邀请其中的零位或更多参加他的聚会。对于每位被邀请的朋友，他们将为聚会带来 $a_i$ 点欢乐度。需要注意的是，部分朋友可能并不热衷于聚会，因此他们的 $a_i$ 值可能为负数。

然而，小帅 的家中仅有一排共 $n$ 个座位，且由于社交距离的考虑，任何两位朋友均不能坐在相邻的座位上。小帅 正在寻求一种最优的邀请方案，以确定在这些限制条件下，被邀请朋友的总欢乐度能达到的最大值。

输入格式

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

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

输出格式

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

5
3 2 -1 4 5

12

1
10

10

6
1 -3 2 10 -4 9

21

提示

【样例 #1 解释】

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

【数据范围】

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