문제1241--Random Sort

### 1241: Random Sort

실행시간 제한: 7 Sec  메모리사용 제한: 128 MB
제출: 66  통과: 27
[제출] [채점기록] [묻고답하기]

#### 문제 설명

You are given a int[] permutation containing a permutation of the first n positive integers (1 through n), and you want to sort them in ascending order. To do this, you will perform a series of swaps. For each swap, you consider all pairs (i, j) such that i < j and permutation[i] > permutation[j]. Among all those pairs, you choose one randomly and swap permutation[i]and permutation[j]. Each pair has the same probability of being chosen. Return the expected number of swaps needed to sort permutation in ascending order.

#### 입력 설명

The first line contains the number of test cases T (T ≤ 200).

For each test case, space-separated two integers n - number of elements in permutation - and n integers as permutation given on the first line.

Constraints

- permutation will contain between 1 and 8 elements, inclusive.
- permutation will contain each integer between 1 and n, inclusive, exactly once, where n is the number of elements in permutation.

#### 출력 설명

Output the answer of each test case on a separate line. You should round the result to sixth digits after the decimal point.

#### 입력 예시 Copy

4
3 1 3 2
4 4 3 2 1
1 1
6 2 5 1 6 3 4

#### 출력 예시 Copy

1.00000
4.06667
0.00000
5.66667