题目描述

在一条环形公路旁均匀地分布着 $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$。

输出格式

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

样例

5
1 8 6 2 5

15

数据范围

$2≤N≤10^6, 1≤A_i≤10^7$

来源

• 算法竞赛进阶指南