题目描述

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

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

在 $i$ 和 $j$ 两座仓库之间运送货物需要的代价为 $A_i + A_j + \text{dist}(i,j)$。

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

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1 \sim A_N$。

输出格式

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

样例

输入样例：

5
1 8 6 2 5

输出样例：

15

样例解释

$N=5$，库存 $A=[1,8,6,2,5]$

计算所有点对 $(i,j)$ 的代价 $A_i + A_j + \text{dist}(i,j)$：

注意距离 $\text{dist}(i,j)=\min(|i-j|,5-|i-j|)$

例如：

• (2,4)：$A_2=8, A_4=2$，距离 $\min(|2-4|=2, 5-2=3)=2$，代价 $8+2+2=12$
• (2,5)：$8+5+\min(3,2)=8+5+2=15$
• (3,5)：$6+5+\min(2,3)=6+5+2=13$
• (2,3)：$8+6+\min(1,4)=8+6+1=15$

最大为 $15$。

数据范围

• $2 \le N \le 10^6$
• $1 \le A_i \le 10^7$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB

所有题目已整理完毕。