Manhattan Sort#2727
Yet another sorting problem! In this one, you are given a sequence of distinct integers and are asked to sort it with minimum cost using only one operation:
The Manhattan swap!
Let S_i and S_j be two elements of the sequence at positions and respectively, applying the Manhattan swap operation to S_i and S_j swaps both elements with a cost of |i-j|. For example, given the sequence \{9, 5, 3\}, we can sort the sequence with a single Manhattan swap operation by swapping the first and last elements for a total cost of (the absolute difference between the positions of and ).
The first line contains an integer , the number of test cases. Each test case consists of lines. The first line contains a single integer (1 \le N \le 30), the length of the sequence . The second line contains space separated integers representing the elements of . All sequence elements are distinct and fit in a -bit signed integer.
For each test case, output one line containing a single integer: the minimum cost of sorting the sequence using only the Manhattan swap operation.
Esempio 1