Goro has 4 arms. Goro is very strong. You don't mess with Goro. Goro needs to sort an array of different integers. Algorithms are not Goro's strength; strength is Goro's strength. Goro's plan is to use the fingers on two of his hands to hold down several elements of the array and hit the table with his third and fourth fists as hard as possible. This will make the unsecured elements of the array fly up into the air, get shuffled randomly, and fall back down into the empty array locations.
Goro wants to sort the array as quickly as possible. How many hits will it take Goro to sort the given array, on average, if he acts intelligently when choosing which elements of the array to hold down before each hit of the table? Goro has an infinite number of fingers on the two hands he uses to hold down the array.
More precisely, before each hit, Goro may choose any subset of the elements of the array to freeze in place. He may choose differently depending on the outcomes of previous hits. Each hit permutes the unfrozen elements uniformly at random. Each permutation is equally likely.
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each one will consist of two lines. The first line will give the number . The second line will list the elements of the array in their initial order.
Output Specification
For each test case, output one line containing Case #x: y
, where is the case number (starting from 1) and is the expected number of hit-the-table operations when following the best hold-down strategy. Answers with an absolute or relative error of at most will be considered correct.
Limits
;
The second line of each test case will contain a permutation of the smallest positive integers.
Memory limit: 1GB.
Small dataset
;
Time limit: 30 seconds.
Large dataset
;
Time limit: 60 seconds.
Sample Input
3
2
2 1
3
1 3 2
4
2 1 4 3
Sample Output
Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000
Explanation
In test case #3, one possible strategy is to hold down the two leftmost elements first. Elements and will be free to move. After a table hit, they will land in the correct order with probability and in the wrong order with probability . Therefore, on average it will take hits to arrange them in the correct order. After that, Goro can hold down elements and and hit the table until and land in the correct order, which will take another hits, on average. The total is then hits.
Note
This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >60.000s
regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.
Comments