All submissions for this problem are available.
Little Johnny has a selection of boxes. Each box has a number on its side. The boxes are placed in a sequence, and Johnny wants to sort them (in ascending order). He has a device to manipulate the boxes, which performs the following operation. Johnny can select a subset of boxes, and the machine will lift the selected subset, shift the selected subset to the right (keeping the order in the subset), shift the not-selected subset to the left, filling up empty spaces (keeping the order in the subset), then finally move the raised boxes to be in one level again.
For example: if Johnny has the sequence: 1,2,3,4,5,6, and selects the subset in bold: 1,2,3,4,5,6, then the result is: 1,2,5,3,4,6.
Help Johnny to write a program that will calculate the minimal number of moves required to sort the given sequence of boxes in ascending order of numbers.
First, 1≤t≤10, the number of test cases. Then, t testcases follow. Each starts with 1≤n≤105, the number of boxes. Then, n integer values describing the sizes of boxes in the sequence.
For each testcase, in a separate line, print the answer to that testcase.
6 1 3 5 2 4 6
|Time Limit:||0.123153 - 0.527692 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.