Indeed Quick Sort

Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O (nlogn) comparisons to sort n items in list T.
Given a list T, the steps are as follows:
1. Randomly pick an element X in list T, called a pivot.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sorts the sub-list of lesser elements and the sub-list of greater elements.
Here we define the cost C of sorting list T to be the sum of the following three parts:
1. The number of elements greater than X on X's left.
2. The number of elements lesser than X on X's right.
3. The cost of recursively sorting the sub-lists.
Could you please tell me what is the expected value of the cost C?

There are multiple test cases. In each test case, the integer N (N<=15000) in the first line gives the number of elements, followed by N integers in the second line describing the elements in the list.

For each test case, print the expected value of cost (rounded after 6 digits after the decimal point) in a single line.

3
1 2 3

0.000000

2011 Multi-University Training Contest 6 - Host by JLU