Sort

Mirko and Slavko, two rising stars of computer science, often pass the time by inventing new algorithms. Right now they are playing with sorting. Mirko proposed the following algorithm:

while (!sorted(A)) { 
      int i = random(N); 
      int j = random(N); 
      if (A[min(i,j)] > A[max(i,j)]) 
            swap(A[i], A[j]); 
}

Inspired by Mirko's version, Slavko proposed this one:

while (!sorted(A)) {
      int i = random(N-1); 
      int j = i + 1; 
      if (A[i] > A[j]) 
            swap(A[i], A[j]); 
}

The function random(k) returns an integer from $0, 1, \ldots, k-1$, and every integer is equally likely. sorted(A) is true when $A$ is in non-decreasing order.

Now they want to know which algorithm is better. Given an array $A$ of length $N$, find the expected number of steps each algorithm needs to finish. One step is one complete iteration of the while loop.

The first line contains the number of elements $N$ of the array $A$ ($1 \le N \le 8$).

The second line contains the $N$ elements $A_1, A_2, \ldots, A_N$ of the array, separated by spaces ($0 \le A_i \le 100$).

On the first line, print the expected number of steps of Mirko's algorithm. On the second line, print the expected number of steps of Slavko's algorithm.

Round each exact expected value to six digits after the decimal point and print exactly six digits after the decimal point. For example, if the expected value is $14.375$, print 14.375000.