All submissions for this problem are available.
Stark has a selection of balls. Each ball has a number on it. The balls are placed in a sequence, and Stark wants to sort them (in ascending order). He has a device to manipulate the balls, which performs the following operation. Stark can select a subset of balls, and the device 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 balls to be in one level again. For example: If Stark has the sequence: 3,5,1,2,8,7,6,4 and selects the subset in bold: 3,5,1,2,8,7,6,4 then the result is: 1,2,7,4,3,5,8,6. Help stark to write a program that will calculate the minimal number of moves required to sort the given sequence of balls in ascending order of numbers. Input First line of input contains the number of test cases t, 1 ≤ t ≤ 10. Then, t test cases follow. Each test case starts with 1 to 105 (the number of balls) followed by the n integer values describing the number on ball in the sequence. Output For each test case, in a separate line, print the answer to that test case i.e. minimum number of moves. Example Input: 1 6 1 3 5 2 4 6 Output: 2
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, CS2, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.