题目背景

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

题目描述

给你一个长度为 $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))$ 的最大值。

3
1 5 2

2

5
-2 3 2 5 3

15

提示

【样例解释】

对于第一个样例，选择 $\{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$。