PROBLEM STATEMENT
You are given a vector <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:vector <int>
Returns:double
Method signature:double getExpected(vector <int> permutation)


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



 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.