랜덤 소트

랜덤 소트는 순열에서 i < j이고 A[i] > A[j]인 위치 쌍을 하나 무작위로 골라 두 원소를 서로 바꾸는 정렬 과정이다.

주어진 순열이 오름차순으로 정렬될 때까지 필요한 교환 횟수의 기댓값을 구하라.

첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열을 이루는 N개의 정수가 주어진다.

각 정수는 1 이상 N 이하이며, 같은 정수는 두 번 이상 주어지지 않는다. N은 8 이하의 자연수이다.

필요한 교환 횟수의 기댓값을 출력한다. 정답과의 절대 또는 상대 오차가 10^-6 이하이면 정답으로 인정된다.