[YNOI2019] 排序
题目描述
对于一个数列 $\{7, 1, 2, 3\}$ 进行排序,我们可以把 $7$ 从头移动到尾。但是这个操作的成本是 $7$,并不是最佳的。最佳的排序方式是将连续的 $1,2,3$ 移动到 $7$ 的前面。这样的话,总的操作成本就是 $1+2+3=6$,比之前的成本 $7$ 要小。
你的任务是,对于一个给定的数列,输出对这个数列进行排序的最小成本。
输入输出格式
输入格式
输入文件名为sort.in。
每个输入文件包含多组数据。
输入文件的第一行,包含一个正整数 $T$,代表该输入文件中所含的数据组数。
接下来是 $T$ 组数据,每组数据的格式如下:
每组数据包含 $2$ 行;
第一行包含一个正整数 $n$,代表数列中元素的个数,其中 $0 < n \leq 10^2$;
第二行包含 $n$ 个整数,两个数之间以一个空格隔开,代表数列中的元素 $k_i$,其中$-10^{7} \leq k_i \leq 10^{7}$。
输出格式
输出文件名为sort.out。
输出文件包含 $T$ 行,分别对应 $T$ 组数据的答案,即对数列进行排序的最小成本。
输入输出样例
输入样例 #1
1
4
7 1 2 3
输出样例 #1
6
说明
对于 $60\%$ 的数据:$0 < n \leq 60$,$-10^{7} \leq k_i \leq 10^{7}$
对于 $80\%$ 的数据:$0 < n \leq 80$,$-10^{7} \leq k_i \leq 10^{7}$
对于 $100\%$ 的数据:$0 < n ≤ 10^2$,$-10^{7} \leq k_i \leq 10^{7}$