极光观测

题目描述

在北极圈的一座观测站里，科学家们正在记录极光的能量强度。连续 $n$ 天，每天的极光强度分别为 $a_i$。

科学家们拥有一台高精度的观测设备，但由于极光能量巨大，每次观测后，设备都需要进行长达两天的“冷却与校准”才能再次使用。也就是说，如果你在第 $i$ 天选择了观测，那么接下来的第 $i+1$ 天和第 $i+2$ 天都不能进行观测，最早只能在第 $i+3$ 天再次进行观测。

为了收集到尽可能多的科学数据，请你计算在这 $n$ 天内，科学家们能够观测到的极光强度之和最大是多少？

输入格式

第一行包含一个整数 $n$，表示总天数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天的极光强度值。

输出格式

输出一个整数，表示观测到的最大极光强度之和。

输入输出样例 #1

输入 #1

6
10 20 30 1 1 50

输出 #1

70

输入输出样例 #2

输入 #2

5
100 1 1 100 1

输出 #2

200

数据范围

对于 $60\%$ 的数据，$1 \le n \le 1000$。

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