Write a C code and write comments.

Ann and King Kong are best friends. King Kong enjoys playing games with Ann, no matter how silly the game is. Once, they were playing a very weird game, Ann arranged N cubes in a straight line on a table, each cube having a unique number in the range 1 to N marked all over it (essentially, the cubes when seen display some permutation of the numbers 1 to N). Now, King Kong bangs the table, the cubes fly in the air, get mixed up uniformly randomly and return to the table. Somehow, the cubes fall on the same straight line every time King Kong bangs the table, just that the positions of the cubes might change. The goal is to finally arrange the cubes such that the numbers on display are sorted in non- decreasing order. Let us assume each time King Kong bangs the table as a round. This game could go on forever. Ann comes up with an idea to speed up the process. Ann can fix (or unfix, if already fixed) any cube to the table, at its position. She can do this to any number of cubes, before any round. When some cubes are fixed and if King Kong bangs the table, the fixed cubes don t fly, hence it s position remains same after that round. Also, the cubes which fly can only return to a position where there is no cube (while in flight) (cubes cannot stack on each other, or go to any other part of the table, or out of the table). Ann wants to complete the game as fast as possible, hence she wants to use this feature optimally. Given a random arrangement of the N cubes, can you find the expected number of rounds required to arrange the cubes in non-decreasing order, given the availability of the feature to fix/unfix cubes? Input: The first line of the input contains a single integer T denoting the number of test cases. T test cases follow. Each test case consists of two lines. The first line contains a single integer N, the number of cubes. The second line contains N space-separated integers, denoting the values on the cubes C, in order of the initial arrangement on the table. Output: For each test case, output one line containing a single number E, denoting the expected number of rounds required to arrange the cubes in non-decreasing order. Your answer must match up to the 6th decimal place. Also, output your answer till 6 decimal places. For example: If your answer is 2.3, output 2.300000. If your answer is 2.345678921, output 2.345678. Constraints: 1 T 100 1 N 1000 1 C N The C; s form a permutation of the numbers 1 to N Sample Input: 2 N N N 2 2 1 4 2 143 Sample Output: 2.000000 4.000000 Explanation: One possible optimal strategy for the second test case, firstly Ann can fix the first two cubes. The expected number of rounds to sort 4 3 in non-decreasing order is 2. Then, unfix the first two cubes and fix the last two cubes. In a similar manner, it takes 2 rounds, in expectation, to sort 2 1 in non-decreasing order. Therefore, in expectation, it takes 4 rounds, in expectation, to sort the entire set of cubes in non-decreasing order.