B-跳跳跳_牛客小白月赛40

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$dd$ 在玩跳格子游戏，具体游戏规则如下，

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

$dd$ 很鸡贼，想赢又不想动脑子，她希望你能给她规划路线以确保她的胜利

输入描述:

第一行一个数n(1≤n≤2000)
接下来一行n个数，表示a[i](1≤a[i]≤2000)

输出描述:

一个数，表示dd可能获得的最高分。
同学请选择语言提交来加快运算速度。

示例1

输入

复制

3
1 1 1

输出

复制

说明

可能方案
1->2->3
1->3->2
2->1->3
2->3->1
3->1->2
3->2->1
(以上数字表示格子标号)
答案均为 1*1+2*1+3*1=6
最优方案不唯一，最优答案唯一

示例2

输入

复制

3
1 2 3

输出

复制

说明

方案:1->2->3（数字对应格子标号）
答案:1*1+2*2+3*3=14
最优方案唯一