解题思路

暴力枚举

1. 枚举所有断开位置 $k=0\ldots n-1$（按0-based下标处理更方便）。
2. 对于每个 $k$，线性扫描长度为 $n$ 的序列，累加求出$S_k$。
3. 取所有 $S_k$ 的最大值即为答案。

由于 $n\le2000$，双重循环最多做 $4\times10^6$ 次乘加运算，完全可行。

题目内容

小红有一个长度为$n$的魔法环,环上依次有数字$a_1,a_2,.,a_n$。她希望通过切开魔法环并对线性序列应用加权

交替求和,得到最终魔法值。操作步骤如下:

1、选定一个断开位置$k(1≦k≦n)$，将环从此位置切开，得到线性序列

$b_1=a_k,b_2=a_{k+1},....$$b_{n-k+1}=a_n,b_{n-k+2}=a1,...,b_n=a_{k-1}$.

2、对得到的线性序列{$bj$}计算加权交替求和:

$S=1·b_1-2·b_2+3·b_3-4·b_4+...+(-1)^{n-1}n·bn$

小红希望在所有可能的断开位置中，$S$的值最大。请你计算并输出此最大值。

输入描述

第一行输入一个整数$n (1≦n≦2000)$，表示魔法环上的数字个数。

第二行输入$n$个整数$a_1,a_2,...,a_n (0≦a_i≦n)$,代表环上各位置的初始数字。

输出描述

输出一个整数，表示小红在所有断开位置的加权交替求和中能获得的最大魔法值。

样例1

输入

4
1 2 3 4

输出

4

说明

当断开位置$k=2$时,序列$[2,3,4,1]$的加权交替求和为 $2-6+12-4=4$,这是所有$S$中的最大值。

样例2

输入

5
1 4 2 3 5

输出

27

说明

当断开位置$k=3$时，序列$[2,3,5,1,4]$的加权交替求和为:

$1×2-2×3+3×5-4×1+5×4=2-6+15-4+20=27$为最大值