P7421 「PMOI-2」子序列

看到这个时限，大家不必恐慌，本题不卡常。

给你一个长度为 $n$ 的序列 $a_i$（**下标从 $1$ 开始**），你需要选出一个 $\{1,2,3,\cdots,n\}$ 的**任意长度非空**的子序列 $p$，设 $p$ 的长度为 $l$，定义 $a_0=p(0)=a_{n+1}=0,p(l+1)=n+1$，你需要最大化： $$\sum_{i=0}^{l}(a_{p(i+1)}-a_{p(i)})(p(l-i+1)-p(l-i))$$ 求出这个最大值。 若 $a$ 是 $b$ 的子序列，则从 $b$ 中删除 $0$ 或多个元素，**按照原顺序**可以得到 $a$，比如 $\{1,4\}$ 是 $\{1,2,3,4\}$ 的子序列，$\{3,1,5\}$ 是 $\{3,1,5\}$ 的子序列，$\{1,2\}$ 不是 $\{3,2,1\}$ 的子序列。

第一行输入一个正整数 $n$，表示 $a$ 的长度。 第二行输入 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出一个整数，表示 $\sum_{i=0}^{l}(a_{p(i+1)}-a_{p(i)})(p(l-i+1)-p(l-i))$ 的最大值。

【样例解释】 对于第一个样例，选择 $\{1\}$ 可以得到最大结果 $(1-0)\times(4-1)+(0-1)\times(1-0)=2$。 对于第二个样例，选择 $\{1,5\}$ 可以得到最大结果 $(-2-0)\times(6-5)+[3-(-2)]\times(5-1)+(0-3)\times(1-0)=15$。 【数据范围】 对于 $20\%$ 的数据，$n\le20$，$0\le a_i\le10^3$； 对于 $50\%$ 的数据，$n\le80$； 对于 $100\%$ 的数据，$1\le n\le300$，$-10^9\le a_i\le10^9$。