James 有 $n$ 个朋友，想要举办一场派对。他想邀请零个或多个朋友，并且他知道只要邀请了他们，他们就会来。每个朋友参加派对会获得 $a[i]$ 的幸福感。注意，有些朋友可能不想参加，其 $a[i]$ 为负数。

他需要为受邀的朋友安排座位，但由于社交距离限制，任何两个朋友都不能坐在相邻的座位上。他总共有 $n$ 个座位，请帮他计算应该邀请哪些朋友，以使他们获得的总幸福感最大化！

输入格式

程序必须从标准输入读取数据。 第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a[i]$，表示每个朋友能获得的幸福感。

输出格式

程序必须输出到标准输出。 输出应包含一个整数，即受邀朋友获得的最大总幸福感。不要打印任何额外文本，例如“Enter a number”或“The answer is”。

子任务

对于所有测试用例，输入满足以下范围：

• $1 \le n \le 200\,000$
• $-10^9 \le a[i] \le 10^9$

程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

5
3 2 -1 4 5

样例输出 1

12

说明 1

James 有 5 个座位。他可以邀请第 1、4 和 5 位朋友并安排他们入座，在他们之间留出空位。

这给他的朋友带来了总计 $a_1 + a_4 + a_5 = 3 + 4 + 5 = 12$ 的幸福感。

样例输入 2

1
10

样例输出 2

10

说明 2

James 可以邀请这位朋友并让他们坐在唯一的座位上，获得 10 的总幸福感。

样例输入 3

6
1 -3 2 10 -4 9

样例输出 3

21

说明 3

James 可以邀请第 3、4 和 6 位朋友并安排他们入座，在他们之间留出空位。

这给他的朋友带来了总计 $a_3 + a_4 + a_6 = 2 + 10 + 9 = 21$ 的幸福感。