在一条环形公路旁均匀地分布着N座仓库，编号为1~N，编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 dist(i,j)=min⁡(|i-j|,N-|i-j|)，也就是逆时针或顺时针从 i 到 j 中较近的一种。

每座仓库都存有货物，其中编号为 i 的仓库库存量为 $A\_i$。

在 i 和 j 两座仓库之间运送货物需要的代价为 $A\_i+A\_j+dist(i,j)$。

求在哪两座仓库之间运送货物需要的代价最大。

输入格式

第一行包含一个整数N。

第二行包含N个整数$A\_1$~$A\_N$。

输出格式

输出一个整数，表示最大代价。

数据范围

$1 \le N \le 10^6$,
$1 \le A\_i \le 10^7$

输入样例：

5
1 8 6 2 5

输出样例：

15

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解