시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

Informatičarske zvijezde u usponu, Mirko i Slavko, često krate vrijeme smišljajući nove algoritme. Trenutno se zabavljaju sortiranjem. Mirko je predložio sljedeći algoritam:

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

Slavko, inspiriran Mirkovom verzijom, predložio je:

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

Funkcija random(k) vraća cijeli broj iz intervala 0, 1, …, k-1 gdje svaki broj ima jednaku vjerojatnost pojavljivanja.

Sada ih zanima koji je algoritam bolji. Za zadani niz A duljine N odredite očekivani broj koraka koji će biti potreban pojedinom algoritmu da se izvrši. Jednim korakom podrazumijevamo jednu potpunu iteraciju while petlje.

입력

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 8), broj elemenata niza A. U sljedećem retku nalazi se N cijelih brojeva A1, A2, …, An (0 ≤ Ai ≤ 100), elementi niza A. 

출력

U prvi redak ispišite očekivani broj koraka algoritma koji je Mirko predložio, a u drugi ispišite očekivani broj koraka algoritma koji je Slavko predložio. Brojeve ispišite sa šest znamenaka iza decimalne točke.

Napomena: Dozvoljeno je odstupanje od službenog rješenja za najviše 10-6

예제 입력

3
3 2 1

예제 출력

6.000000
5.000000

예제 입력 2

6
2 7 1 8 2 8

예제 출력 2

33.000000
14.375000

힌트