CF1859C Another Permutation Problem

Andrey 刚开始出题，这对他来说很难。因此他想出了一个关于排列的奇怪问题，并请你来解决。你能做到吗？ 我们定义一个长度为 $n$ 的排列 $p$ 的代价为以下表达式的值： $ (\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j) $。请你求出所有长度为 $n$ 的排列中代价的最大值。 $ ^{\dagger} $ 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个互不相同的整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中有 $4$）。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 30$）——表示测试数据的组数。接下来每组测试数据包含一行，一个整数 $n$（$2 \le n \le 250$）——表示排列的长度。 保证所有测试数据中 $n$ 的总和不超过 $500$。

对于每组测试数据，输出一个整数，表示所有长度为 $n$ 的排列中代价的最大值。

在第一个测试点中，最大代价的排列是 $[2, 1]$。其代价为 $2 \cdot 1 + 1 \cdot 2 - \max(2 \cdot 1, 1 \cdot 2) = 2 + 2 - 2 = 2$。 在第二个测试点中，最大代价的排列是 $[1, 2, 4, 3]$。其代价为 $1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$。 由 ChatGPT 4.1 翻译