题目内容

山路一共设有 $n$ 个关卡，按 $1 \sim n$ 顺序排列。当前位于 $1$ 号关卡，必须按照关卡从小到大闯关，且必须到达最后第 $n$ 号关卡才算寻宝成功。每个关卡都有对应的宝藏分值(可能为负数)，经过当前关卡即可获得该关卡分值，分数持续累加。

移动规则：

1. 从当前关卡，下一次只能在前方 $1$ 关或者 $2$ 关处打卡；
2. 限制规则：不能连续两次都一次性跳 $2$ 关，违反该规则的路线无效；

请求出：所有合法路线中，能够收集到的最大累加总分。

输入描述

参数1：整数 $n$，代表关卡数量

参数2：整数数组，依次表示第 $1 \sim n$ 关的宝藏分值

$1 \leq n \leq 20$

每关分值：$-999 \leq val \leq 999$

输出描述

输出一个整数，代表合法路线的最大累加得分。

样例1

输入

5,[10,5,8,3,15]

输出

41

说明

• 合法路线示例：$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$，无连续跳两关，总分：$10+5+8+3+15 = 41$
• 路线 $1 \rightarrow 3 \rightarrow 5$ 连续两次跳 $2$ 关，违规，不计入统计。

样例2

输入

4,[10,1,1,100]

输出

112

说明

• 路线 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ $(1,1,1)$: $10+1+1+100=112$
• 路线 $1 \rightarrow 3 \rightarrow 4$ $(2,1)$: $10+1+100=111$
• 路线 $1 \rightarrow 2 \rightarrow 4$ $(1,2)$: $10+1+100=111$
• 最大值 $112$。