该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师上次买了一只机器青蛙，玩腻了。

本着节约的原则，他重新写了程序，烧到青蛙的固件中。

这次，青蛙的跳动方式和前一次不同了。

每次青蛙都会向上跳 $A$ ，向下跳 $B$ ，再向上跳 $A$ ，向下跳 $B$。

由于青蛙学习过石老师的 STL 课程，精通 set ，所以不愿意在同一个位置出现两次。如果发生，就认为是对它智商的侮辱，直接跳崖自尽。

那么问题来了，如果徐老师把这只青蛙放到世界遗产-泰山的第一级台阶上，让青蛙顺着台阶往上跳到山顶（位于第$N（3 \leq N \leq 10^5）$ 级） 。不能跳过头，否则青蛙会摔破，里面的分数清零。

每一级台阶上都有一个分数$s_i（-10^9 \leq s_i \leq 10^9）$，徐老师坐缆车到达山顶，如果选择合适的 $A$ 和 $B$ ，青蛙的最大得分是多少。

起点和终点处没有分数。

Format

Input

第一行一个正整数 $N$ 。

第二行 $N$ 个整数 $s_1$ 、 $s_2$ $\ldots$ $s_N$ 。

Output

输出最大得分。

Samples

5
0 2 6 1 0

3

Limitation

1s, 1024KiB for each test case.