题目描述

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

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

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

格式

输入格式

第一行为一个正整数 \(N\)。

第二行有 \(N\) 个用空格隔开的 \(N\) 个不同的正整数。

输出格式

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

样例1

输入样例1

6
54 29 196 21 133 118

输出样例1

768

样例解释

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

限制

\(100\%\)的数据：\(3 ≤ N ≤ 100\)，\(N\) 个操作数为\(1 \sim 1000 \)之间的整数。