Problem Description

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.

Input Format

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}$.

Output Format

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

1
4
7 1 2 3

6

Hint

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