题目描述

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

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

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

输入格式

第一行为一个正整数 $N$ ； 第二行有 $N$ 个用空格隔开的 $N$ 个不同的正整数。 数据规模：$3 \le N \le 100$，$N$个操作数为 $1 \sim 1000$ 之间的整数。

输出格式

一行，包含一个正整数，为操作的最大值。

6
54 29 196 21 133 118

768

样例说明

样例说明，经过 $3$ 次操作可以得到最大值：

• 第一次去掉前面 $3$ 个数 $54,29,196$ ，操作价值为 $426$ 。
• 第二次操作是在剩下的三个数 $21,133,118$中去掉最后一个数 $118$ ，操作价值为 $118$ 。
• 第三次操作去掉剩下的 $2$ 个数 $21$ 和 $133$ ，操作价值为 $224$ 。

操作总价值为 $426+118+224=768$ 。