P5414 [YNOI2019] Sorting

To sort a sequence $\{7, 1, 2, 3\}$, we can move $7$ from the beginning to the end. However, the cost of this operation is $7$, which is not optimal. The optimal way is to move the consecutive segment $1,2,3$ to the front of $7$. In this case, the total cost is $1+2+3=6$, which is smaller than the previous cost $7$. Your task is: for a given sequence, output the minimum cost to sort this sequence.

Each input file contains multiple test cases. The first line contains a positive integer $T$, which represents the number of test cases in the input file. Then follow $T$ test cases, each in the following format: Each test case contains $2$ lines. The first line contains a positive integer $n$, which represents the number of elements in the sequence, where $0 < n \leq 10^2$. The second line contains $n$ integers separated by a single space, representing the elements $k_i$ of the sequence, where $1 \leq k_i \leq 10^{7}$.

The output file contains $T$ lines, each corresponding to the answer for one test case, i.e., the minimum cost to sort the sequence.

Constraints: For $60\%$ of the testdata: $0 < n \leq 60$, $1 \leq k_i \leq 10^{7}$. For $80\%$ of the testdata: $0 < n \leq 80$, $1 \leq k_i \leq 10^{7}$. For $100\%$ of the testdata: $0 < n \leq 10^2$, $1 \leq k_i \leq 10^{7}$, $0 < T \leq 10$. Translated by ChatGPT 5