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

题目背景

小明作为班长，要筹备这次的主题班会。班主任给了小明几个任务。

题目描述

主题班会结束后会进行一个小游戏。首先挑选 $n$ 名同学出来组成队伍，排成一排，并且每个人在背后贴一张写有数字的卡片 $a_i$（数字可能不同）。

然后从剩下的学生中随机挑选一个加入队伍，允许他自由选择要加入到队伍的哪个位置。加入队伍后，奖励给这个学生他左右两边同学背后卡片数字之和同等数量的糖果。

请问这名学生最多能获得几个糖果？

输入格式

第一行一个整数 $n$，表示站成一排的学生人数

接下来 $n$ 行，每行一个整数，对应从左到右每个学生背后卡片的数字 $a_i$。

输出格式

一个整数，表示这名学生最多能获得的糖果数量。

样例数据

6
8
3
4
8
2
9

12

样例 1 解释

这名学生选择站在 $4$ 和 $8$ 这两名学生之间，能获得最多糖果。

数据范围

对于 $20\%$ 的数据，所有卡片数字都相等；

另有 $20\%$ 的数据，从左到右卡片数字递增；

对于全部数据，$1 \le n \le 1000, 0 \le a_i \le 1000$。