题目背景

$fish$在$7$月末参加了信奥夏令营。可麻烦的是一直连续做邵脑题。一天下午，窗外下起了暴雨。 暴雨下了一天一夜，导致$fish$所在的集训营被洪水淹了。而$fish$可以通过洪水重获新生。

题目描述

集训营被洪水分割成 $n$ 层，每层通道有一个氧气值$a_i$（可正可负，正代表获取氧气，负代表消耗氧气）。 $fish$ 从第 $1$ 层出发，需要到达第 $n$ 层完成逃生，移动规则如下：

1. 每次可以向上爬 $1$ 层 或 ​向上爬 $2$ 层​（只能向第 $n$ 层方向移动，不能回头）；
2. 到达某一层时，​必须获取 / 消耗该层的氧气​；
3. 最终到达第 $n$ 层时，需要让总肺活量(氧气)​最大化​（重获新生的关键）。

你的任务是计算：$fish$ 完成逃生能获得的​最大氧气值​。

输入格式

第一行：一个整数 $n(2 \le n \le 10^{5})$，表示试炼通道的层数； 第二行：n 个整数 $a_1,a_2,a_3,...,a_n (-10^{4} \le a_i \le 10^{4})$ ，表示每层的氧气值。

输出格式

一个整数，表示能获得的最大总氧气。

样例

5
1 -2 3 4 -1

7

限制

• 1s
• 1024KiB.

提示

• 对于 100% 的数据：$2 \le n \le 3×10^{5},-10^{4} \le a_i \le 10^{4}$