Random Sort

Random sort is a sorting process on a permutation. At each step, choose one pair of positions i < j with A[i] > A[j] uniformly at random, then swap the two elements.

Given a permutation, compute the expected number of swaps needed until it becomes sorted in increasing order.

The first line contains the size N of the permutation. The second line contains the N integers of the permutation.

Each integer is between 1 and N, inclusive, no value appears more than once, and N is a positive integer at most 8.

Output the expected number of swaps needed. An absolute or relative error of at most 10^-6 is accepted.