3. Railway Sort (done)

The “Railway Sort” is a sorting algorithm based on the metaphor of arranging the cars of a train into the correct order. Your one move in a Railway Sort is to remove a “car” from the “train” by shunting it onto a side rail, then reattach the two pieces, move the train forward and reattach the car onto the back end of the train. The cost of such a move is proportional to the number of positions you moved the shunted train car.

In the example at the left, car 1 is shunted out and then reattached at the back end of the train (which is on the left because the train in this example is moving rightwards). The cost of this move is 2 because the car had to move 2 positions. The cost of sorting this train into ascending order is also 2 since the car numbers are now sorted correctly. If this sort had required more moves, the total cost would have been the sum of the cost of each of the moves.

DATA31.txt (DATA32.txt for the second try) will contain 10 test cases. The first line of each test case will consist of a single integer 𝑁𝑁 indicating the number of cars in the train, where 1≤ 𝑁𝑁≤ 1000. The next line will contain all of the integers from 1 to 𝑁𝑁 arranged in some random order, separated by spaces.

Each integer will appear exactly once. For each of the 10 test cases, you must print the minimum cost of performing a Railway Sort to arrange the integers into ascending order.

Note that the sample data below only contains 2 test cases but the test data will contain 10.

Sample Input

5

3 5 1 4 2

10

2 4 6 8 10 1 3 5 7 9

Sample Output

12

67

Pseudocode

lines = Read all lines into the array

counter = 0

numMoves = 0