### Problem Statement

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.

### Definition

 Class: RandomSort Method: getExpected Parameters: int[] Returns: double Method signature: double getExpected(int[] permutation) (be sure your method is public)

### Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.

### 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.

### Examples

0)

 `{1,3,2}`
`Returns: 1.0`
 Exactly one swap is needed.
1)

 `{4,3,2,1}`
`Returns: 4.066666666666666`
 In the first step, any two elements can be swapped.
2)

 `{1}`
`Returns: 0.0`
 This permutation is already sorted, so there's no need to perform any swaps.
3)

 `{2,5,1,6,3,4}`
`Returns: 5.666666666666666`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8590

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12174&pm=8590

srbga

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky , Gassa

#### Problem categories:

Dynamic Programming, Simple Math