랜덤 소트 2

랜덤 소트는 크기가 $N$인 순열 $P$를 다음 알고리즘으로 정렬하는 방법이다.

function random_sort(permutation P) {
	swaps = 0;
	while (not sorted P) {
		(i, j) = random pair (1 <= i < j <= N)
		swap(P[i], P[j])
		swaps = swaps + 1;
	}
	return swaps;
}

random pair는 $1 \le i < j \le N$을 만족하는 쌍 $\binom{N}{2}$개 중 하나를 매번 독립적으로, 같은 확률로 고른다. $P$가 오름차순이 되면 반복을 멈추고 그때까지 센 교환 횟수를 반환한다.

순열 $P$가 주어졌을 때 random_sort가 반환하는 값의 기댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 순열의 크기 $N$ ($2 \le N \le 10$)이 주어진다.

둘째 줄에 순열 $P_1, P_2, \dots, P_N$이 공백으로 구분되어 주어진다. $1$부터 $N$까지의 정수가 각각 정확히 한 번씩 나타난다.

random_sort가 반환하는 값의 기댓값을 소수점 아래 일곱째 자리까지 출력한다. 여덟째 자리에서 반올림하고, 자리가 남으면 $0$으로 채운다. 입력 순열이 이미 오름차순이면 0.0000000을 출력한다.