题目描述

ak机小时候很喜欢一个叫跳格子的游戏，地上总共有$n$几个格子，ak机跳到第$i$个格子可以获得$a_i$的分数。 ak机从第1个格子开始，ak机每次可以跳跃一个悲波那契数的长度，她想知道她恰好跳到第$n$个格子最多可以获得多少分。 所谓斐波那契数，指斐波那契数列:1,1,2,3,5,8.….中的某一项。悲波那契数列满足，第三项开始，每一项等于前两项之和。

输入描述

第一行输入一个整数$n(1\le n \le 2\times 10^5)$表示数组长度。

第二行输入$n$个整数表示每个格子的分数$a_i(-10^9\le a_i\le 10^9)$

输出描述

输出一个整数表示答案:

样例1

输入

3
1 2 3

输出

6

说明

第1步，跳跃1格，跳到第2个格子
第2步，跳跃1格，跳到第3个格子。
获得的分数为6。

样例2

输入

3
1 -2 3

输出

4