## ECOO '16 R1 P3 - Railway Sort

View as PDF

Points: 8 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 Railway Sort is to remove a "car" from the "train" by shunting it 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 above, car 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 because the car had to move positions. The cost of sorting this train into ascending order is also 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.

The input will contain test cases.

The first line of each test case will consist of a single integer indicating the number of cars in the train, where . The next line will contain a permutation of all of the integers from to , separated by spaces.

For each of the 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 test cases but the test data will contain .

#### Sample Input

5
3 5 1 4 2
10
2 4 6 8 10 1 3 5 7 9

#### Sample Output

12
67

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org