CF1580D Subsequence

Alice 有一个长度为 $n$ 的整数序列 $a$，所有元素都是不同的。她将选择一个长度为 $m$ 的 $a$ 的子序列，并将一个子序列 $a_{b1},a_{b2},...,a_{bm}$ 的价值定义为 $$\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m f(\min(b_i, b_j), \max(b_i, b_j))$$ 其中 $f(i,j)$ 表示 $\min(a_i,a_{i+1},..., a_j)$。 Alice 希望你能帮助她将她所选择的子序列的价值最大化。 如果一个序列 $s$ 可以通过删除序列 $t$ 中几个元素（可以不删除任何元素或删除全部元素）得到，那么这个序列 $s$ 就是序列 $t$ 的一个子序列。

无

无

### 样例解释 在第一个例子中，Alice 可以选择子序列 $[15, 2, 18, 13]$ , 该子序列的值为 $4 \cdot (15 + 2 + 18 + 13) - (15 + 2 + 2 + 2) - (2 + 2 + 2 + 2) - (2 + 2 + 18 + 12) - (2 + 2 + 12 + 13) = 100$。 在第二个例子中，有多种价值为 $176$ 的子序列，其中一个是 $[9,7,12,20,18]$。