Random Sort

Time limit2sMemory limit128 MB

Summary

Compute the expected number of random inversion swaps needed to sort a permutation of size at most 8 into increasing order.

Level: Hard8 of 10
Topics: Probability, Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

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.

Input

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

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

Examples4

Example 1
Input
```
3
1 3 2
```
Expected output
```
1.0
```
Example 2
Input
```
4
4 3 2 1
```
Expected output
```
4.066666666666666
```
Example 3
Input
```
1
1
```
Expected output
```
0.0
```
Example 4
Input
```
6
2 5 1 6 3 4
```
Expected output
```
5.666666666666666
```