题目描述

一位科学家在研究环形魔法阵时，沿其边缘等距摆放了若干有地脉力量的魔法水晶。为了启动魔法阵，他需要将其中一些水晶改造为魔力装置，而剩下的水晶则会被触发并产生能量。

科学家发现，每个被触发的水晶的能量强度 $P$ 取决于它到最近的魔力装置的特殊距离 $d_{min}$ ，并给出了一个关系数组 $a$ ，其中：

• $d_{min}$ 表示这个魔法水晶和最近的魔力装置之间有几个魔法水晶。

• $a[i]$ 表示当 $d_{min}=i$ 时，该水晶的能量强度 $P=a[i]$ 。

由于魔法阵是环形的，水晶的排列是循环的(即首尾相连)。身为科学家的助手，你的任务是知道所有改造方案里，魔法阵产生最大能量强度 $P$ 是多少。

输入格式

每个测试文件仅有一组测试数据。

第一行输入一个整数 $n$ ($1\le n\le 5000$)，代表环形上魔法水晶的数量。

第二行包含 $n$ 个正整数 $a_0 ,\ a_1 ,\ a_2 \ ...,\ a_{n-1}$ ($1\le a_{i}\le 10^{9}$)，代表距离 $d_{min}=i$ 的强度 。

输出格式

输出一行一个整数，表示最大可以产生的能量强度 $P$ 。

7
10 10 1 1 1 1 1

50

解释 #1

在样例一中，特殊距离为 $0$ 和 $1$ 都可以提供10点能量，所以改造后布置为下面的情况最大 ( $1$ 为魔力装置, $0$ 为水晶)：

因为是环形的，所以每个位置的情况为：

• 第 $1$ 个是魔力装置，所以不提供能量；
• 第 $2$ 个是水晶，$d_{min}=min(0,3)=0$ ，所以提供 $a_0=10$ 能量；
• 第 $3$ 个是水晶，$d_{min}=min(1,2)=1$ ，所以提供 $a_1=10$ 能量；
• 第 $4$ 个是水晶，$d_{min}=min(2,1)=1$ ，所以提供 $a_1=10$ 能量；
• 第 $5$ 个是水晶，$d_{min}=min(3,0)=0$ ，所以提供 $a_0=10$ 能量；
• 第 $6$ 个是魔力装置，所以不提供能量；
• 第 $7$ 个是水晶，$d_{min}=min(0,0)=0$ ，所以提供 $a_0=10$ 能量；

所以最终答案为 $50$。