Manhattan Sort

Yet another sorting problem! In this one, you’re given a sequence S of N distinct integers and are asked to sort it with minimum cost using only one operation:
The Manhattan swap!
Let Si and Sj be two elements of the sequence at positions i and j respectively, applying the Manhattan swap operation to Si and Sj 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 2 (absolute difference between positions of 9 and 3).

The first line of input contains an integer T, the number of test cases. Each test case consists of 2 lines. The first line consists of a single integer (1 <= N <= 30), the length of the sequence S. The second line contains N space separated integers representing the elements of S. All sequence elements are distinct and fit in 32 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.

2
3
9 5 3
6
6 5 4 3 2 1

Case #1: 2
Case #2: 9

The Third Lebanese Collegiate Programming Contest