题目描述

一年一度的美食比赛火热进行中，小珅作为评委需要对一些选手的菜品打分，所有菜品从左到右排成一排，编号依次为 1∼n，第 i 个菜品的美味值是 $d_i$。小珅可以自己选择对那些选手的菜品进行打分，但是必须满足以下两个条件：

① 至少选择两位选手的菜品；

② 选择的第一个选手和最后一位选手的菜品美味值必须相同。

小珅所选的第一个菜品和最后一个菜品之间（不包含第一个和最后一个菜品）的部分菜品可以选择不要，请你帮助小珅计算所选菜品美味值的总和的最大值是多少？

输入格式

第一行一个整数 n；

第二行 n 个整数 $d_{1}$,$d_{2}$,…,$d_n$。

输出格式

一行一个整数，表示所选菜品美味值的总和的最大值。

样例输入

5
1 2 3 1 2

样例输出

8

提示

对 100% 的数据保证：$2\le n\le 2\times 10^{5}$，$-10^{9}\le d_i\le 10^{9}$。

2
3 3

6

3
1 2 1

4

4
7 7 7 7

28