608. 删数

【问题描述】

有 N 个不同的正整数数 x 1 , x 2 , ... x N 排成一排，我们可以从左边或右边去掉连续的 i 个数（只能从两边删除数）， 1<=i<=n ，剩下 N-i 个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。

每次操作都有一个操作价值，比如现在要删除从 i 位置到 k 位置上的所有的数。操作价值为 |x i – x k |*(k-i+1) ，如果只去掉一个数，操作价值为这个数的值。

任务

如何操作可以得到最大值，求操作的最大价值。

Input Data

输入文件 remove.in 的第一行为一个正整数 N ，第二行有 N 个用空格隔开的 N 个不同的正整数。

Output Data

输出文件 remove.out 包含一个正整数，为操作的最大值

约束和提示

3<=N<=100
N 个操作数为 1..1000 之间的整数。
样例

remove.in

6
54 29 196 21 133 118

remove.out

768

说明：经过 3 次操作可以得到最大值，第一次去掉前面 3 个数 54 、 29 、 196 ，操作价值为 426 。第二次操作是在剩下的三个数（ 21 133 118 ）中去掉最后一个数 118 ，操作价值为 118 。第三次操作去掉剩下的 2 个数 21 和 133 ，操作价值为 224 。操作总价值为 426+118+224=768 。