徐老师的玩具模型 1556

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：25 AC：11 Score：100

Description

徐老师的家里摆了一整排的玩具模型，编号分别为 $1,2,3 \dots n$，但是数量实在是太多了，于是石老师决定拿走一些，留下一些

可是徐老师非常喜欢它的玩具们，百般请求希望石老师多留下一些

于是石老师提出了一个要求：在不允许移动玩具的情况下，徐老师可以留下任意玩具模型，但是最后不能有三个连续编号的玩具模型存在

徐老师对每个玩具有一个喜爱度 $a_i$，徐老师希望使留下的玩具模型的喜爱度之和尽可能大，请你帮帮他

Input

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

第二行包含 $n$ 个整数 $a_i$，表示徐老师对每个玩具的喜爱度

对于 $30\%$ 的数据，$3 \leq n \leq 20, 1 \leq a_i \leq 10 ^ 3$

对于 $100\%$ 的数据，$3 \leq n \leq 10 ^ 5, 1 \leq a_i \leq 10 ^ 9$

Output

输出一行，包含 $1$ 个整数，表示徐老师能留下玩具模型的喜爱度最大是多少

Samples

input:

4 1 2 3 4

output: