## VM7WC '15 #1 Silver - Jung Goon

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
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

Junghoon Jugoon Jung Goon, in an attempt to impress Mr. White, has decided to perform a complex magic trick. He starts out by laying cards face down on a table in a straight line. Each card has a number such that the cards form some permutation of the numbers . However, since Jung Goon has a photographic memory, he knows the exact order of his cards. His trick involves making a series of swaps, where he switches the positions of two adjacent cards. Since he is a computer science student, he wishes to use as few swaps as possible to sort the line of cards into the order . Help him compute the minimum number of swaps required to sort the cards.

#### Input Specification

The input contains on the first line the number of test cases . Each test case consists of two input lines. The first line of a test case contains an integer , determining the number of cards. The second line of a test case contains a permutation of the numbers through , indicating the current order of the cards.

#### Output Specification

For each test case, print the minimum number of swaps needed to sort the cards.

#### Sample Input

3
3
1 3 2
4
4 3 2 1
2
2 1

#### Sample Output

1
6
1

• commented on June 10, 2019, 4:27 p.m.

just counting the number of inversions in the array should be sufficient right .

• commented on Nov. 6, 2016, 9:37 a.m.

Where do these questions come from-what is the VMSS 7 week challenge, and where is it run?

• commented on July 10, 2015, 2:57 p.m.