정렬

정보과학계의 떠오르는 별인 미르코와 슬라브코는 새로운 알고리즘을 궁리하며 시간을 보내곤 한다. 요즘 두 사람은 정렬에 푹 빠져 있다. 미르코는 다음 알고리즘을 제안했다.

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]); 
}

미르코의 알고리즘에서 영감을 얻은 슬라브코는 다음 알고리즘을 제안했다.

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

함수 random(k)는 $0, 1, \ldots, k-1$ 중 하나의 정수를 반환하며, 각 정수가 나올 확률은 모두 같다. sorted(A)는 $A$가 오름차순(같은 값이 이웃해도 된다)으로 정렬되어 있을 때 참이다.

두 사람은 이제 어느 알고리즘이 더 나은지 궁금해졌다. 길이가 $N$인 배열 $A$가 주어질 때 각 알고리즘이 끝날 때까지 걸리는 단계 수의 기댓값을 구하시오. 한 단계는 while 루프를 한 번 완전히 반복하는 것을 뜻한다.

첫째 줄에 배열 $A$의 원소 개수 $N$이 주어진다. ($1 \le N \le 8$)

둘째 줄에 배열 $A$의 원소 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다. ($0 \le A_i \le 100$)

첫째 줄에 미르코가 제안한 알고리즘의 단계 수 기댓값을, 둘째 줄에 슬라브코가 제안한 알고리즘의 단계 수 기댓값을 출력한다.

각 값은 정확한 기댓값을 소수점 아래 일곱째 자리에서 반올림하여 소수점 아래 정확히 여섯 자리로 출력한다. 예를 들어 기댓값이 $14.375$이면 14.375000을 출력한다.