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:</p>

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 A₁, A₂, …, A_n (0 ≤ A_i ≤ 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.</p>

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

예제 입력 1

3
3 2 1

예제 출력 1

6.000000
5.000000

예제 입력 2

6
2 7 1 8 2 8

예제 출력 2

33.000000
14.375000