题目描述

小理在玩跳格子游戏，具体游戏规则如下:

$n$ 个格子呈环形分布，顺时针方向分别标号为 $1\sim n$ ，其中 $1$ 和 $n$ 相邻，每个格子上都有一个正整数 $a[i]$ ，玩家可以选择一个点作为起点开始跳 $n$ 下，第 $i$ 次跳跃，玩家只可以选择当前位置左边或右边最近且尚未被跳跃过的位置进行一次跳跃，并获得 $i\times a[p]$ 的得分，其中 $p$ 为第 $i$ 次跳跃的位置。

小理很鸡贼，想赢又不想动脑子，他希望你能给他规划路线以确保他的胜利。

输入格式

第一行一个数n。

接下来一行 $n$ 个数，表示 $a[i]$ 。

输出格式

一个数，表示小理可能获得的最高分。

样例输入输出

样例输入#1

3
1 1 1

样例输出#1

6

样例输入#2

3
1 2 3

样例输出#2

14

数据范围

对于 $100%$ 的数据，保证 $1≤n≤2000,1≤a[i]≤2000$ 。

提示说明

样例# $1$ :

可能方案

$1->2->3$

$1->3->2$

$2->1->3$

$2->3->1$

$3->1->2$

$3->2->1$

(以上数字表示格子标号)

答案均为 $11+21+3*1=6$

最优方案不唯一，最优答案唯一

样例# $2$ :

方案: $1->2->3$（数字对应格子标号）

答案: $11+22+3*3=14$

最优方案唯一