1.删数问题

题目描述

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

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

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

输入格式

第一行为一个正整数$N$，第二行有$N$个用空格隔开的$N$个不同的正整数。

输出格式

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

数据范围与提示

对于$100\%$的数据，$3 \leq N \leq 100$，$N$个操作数为$1$到$1000$之间的整数。

样例

6
54 29 196 21 133 118

768