Problem G
John's Book Stack

John has a big stack of books of various sizes. Such a stack is stable if the books have non-decreasing sizes (viewed from top to bottom); otherwise, it is unstable, and likely to fall over.

To prevent this, John wants to sort the books in the stack by size. He does so by pulling out a book from somewhere in the middle (or bottom) of the stack and then putting it back on top. However, he can only pull out a book safely if the books on top of it already form a stable stack.

For example, if John has a stack of four books with sizes 3, 4, 1 and 2 (from top to bottom) then he can sort them as follows:

\includegraphics[width=0.8\textwidth ]{example}

Your task is to determine how many steps are required to sort a given stack of books. In the example above, which corresponds to the first sample case, the answer is 3.


On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with an integer $n$ ($1 \le n \le 50$): the number of books.

  • one line containing $n$ space-separated integers $s_ i$ ($1 \le s_ i \le 1\, 000$ for $1 \le i \le n$): the sizes of the books, as they appear in the initial stack from top to bottom.


Per test case:

  • one line with an integer: the minimum number of steps required to sort the stack using the algorithm described above.

Sample Input 1 Sample Output 1
3 4 1 2
3 1 4 1 5 9 2 6
1 42 42 42 1000
4 1 2 5 6 7 9 10 3 13 17 11 12 14 19 20 22 8 15 16 18 21

Please log in to submit a solution to this problem

Log in