SP676 LSORT - Sorting is not easy

一个 $N$ 元素的排列是指一个元素各不相同且均来自集合 ${1,2,\cdots,n}$ 的序列。例如，序列 $2,1,4,5,3$ 是一个 $5$ 元素的排列。$P$ 是一个 $N$ 元素的排列。你的任务是将 $P$ 排序成升序。但因为这很简单，所以我有一个新的规则给你。你有两个序列 $P$ 和 $Q$。$P$ 是一个 $N$ 元素的排列， $Q$ 最初是空集，通过排序 $P$ 形成（例子：最后 $Q={1,2,3,\cdots,N}$）。你需要操作 $N$ 次来排序 $P$。在第 $i$ 步，$P$ 有 $N-i+1$ 个剩余的元素，$Q$ 有 $i-1$ 个元素。你需要选择 $P$ 的第 $x$ 个元素（从剩余的 $N-i+1$ 可选择的元素）来放在 $Q$ 的左端或右端。这一步的代价是 $x * i$。总花费是所有步骤的代价总和。在 $N$ 步后，$Q$ 必须是一个升序的序列。你的任务是求出总花费的最小值。

**本题目有多组测试。** 输入第一行是 $T(T\le10)$，表示有 $T$ 组需要你进行实验的数据。接下来是 $T$ 组测试数据。 每组测试数据包括两行。第一行包含一个整数 $ N (1 \le N\le1000) $ 。第二行包含 $N$ 个属于 ${1,2,\cdots,N}$ 不同的整数，表示 $N$ 元素序列 $P$。

对于每一组数据，输出需要的最小花费。 ## 样例 ### 样例输入 #1 ``` 1 4 4 1 3 2 ``` ### 样例输出 #1 ``` 15 ``` ### 样例解释 $N = 4$ $P = \{4,1,3,2\}$ 第一步：选择第三个，$P=\{4,1,2\}$，$Q=\{3\}$，代价=$3$。 第二步：选择第一个，$P=\{1,2\}$，$Q=\{3,4\}$，代价=$2$。 第三步：选择第二个，$P=\{1\}$，$Q=\{2,3,4\}$，代价=$6$。 第四步：选择第一个，$P=\varnothing$， $Q=\{1,2,3,4\}$ ， 代价=$4$。 总花费为$15$。 另一种排序的方法： 第一步：选择第四个，$P=\{4,1,3\}$，$Q=\{2\}$ ， 代价=$4$。 第二步：选择第二个，$P=\{4,3\}$， $Q=\{1,2\}$ ， 代价=$4$。 第三步：选择第二个，$P=\{4\}$， $Q=\{1,2,3\}$ ， 代价=$6$。 第四步：选择第一个，$P=\varnothing$，$Q=\{1,2,3,4\}$ ， 代价=$4$。 总花费为$18$。