题目描述

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

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

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

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

输入格式

第一行包含一个整数$\red {N}$。

第二行包含$\red {N}$个整数$\red {A_1~ ~A _N~}$ 。

输出格式

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

样例

输入样例

5
1 8 6 2 5

输出样例

15

提示

$\red {1≤N≤10^6}$,

$\red {1≤A_i≤10^7}$