精灵王国要同侵略 $Bzeroth$ 大陆的地灾军团作战了。

众所周知，精灵王国有 $N$ 座美丽的城市，它们以一个环形排列在 $Bzeroth$ 的大陆上。

为了补充军需，王国财政部决定从这 $N$ 座城市的商人们腰包中征用物资，其中第 $i$ 座城市的商人们共可以提供 $A_i$ 单位的物资。

当征粮队征集物资的时候，他们发现一件出乎意料的事情：如果他们征集了第 $i$ 座城市的物资，那么与第 $i$ 座城市相邻的两座城市（ $1$ 号城市与 $N$ 号城市相邻）里的商人都会逃跑，即征粮队不能再到这两座城市征集物资。

财政部得知这一消息后迅速召开了会议，决定让精灵王国最好的工程师——你，来设计出最优的征集方案，使得联军能够征集到的物资尽可能多。

输入格式

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

第二行 $N$ 个正整数，第 $i$ 个数为 $A_i$。

输出格式

输出最优情况下征集到的物资总和。

样例

input

5
2 3 4 5 5

output

9

explanation

征集第 $3$ 座和第 $5$ 座城市的物资。

限制与约定

对于 $50\texttt{%}$ 的数据：$1 \leq N \leq 20$。

对于 $70\texttt{%}$ 的数据：$1 \leq N \leq 2501$。

另有 $20\texttt{%}$ 的数据：所有 $A_i$ 均相等。

对于 $100\texttt{%}$ 的数据：$1 \leq N \leq 152501$，$1 \leq A_i \leq 10^9$ 。

时间限制：$1\texttt{s}$

空间限制：$128\texttt{MB}$