// The "CCC2005s5PinballRankingMerge" class.
//
// this solution is due to Sean Henderson of University of Toronto
//
// the insight is that rank for score x is essentially
// the number of inversions from 0 to x (plus 1). An inversion
// is when a[x] > a[y] when x < y.
// so if the total inversions for the entire array is I
// the average rankings is (I + N) / N
//
// The number of inversions of the array can be determined
// by using merge sort. The idea is if you are merging
// a[x,y) with a[y,z) then the number of inversions is the total
// of the number of elements in a[x,y) each time one is taken
// from a[y,z).
//
// For example suppose you were sorting:
// 5 8 2 5 7 1
//
// after 1 pass it would be
// 5 8 2 5 1 7 with a total = 1 because there was 1 case
// where the 7 and 1 were out of order
//
// on the second pass 5 8 and 2 5 are merged together
// in this case the total = 2 (5 8 versus 2) plus 1
// (for the 8 versus 5)
// total inversions so far is 4, and the array looks like
// 2 5 5 8 1 7
//
// on the last pass the total = 4 (2558 vs 1) plus 1
// (for the 8 vs 7)
// giving a grand total inversions of 9.
//
// the average rankings is then (9+6)/6 = 2.5
//
// this is correct because the rankings found normally are:
// (1 + 1 + 3 + 2 + 2 + 6) / 6 = 2.5
import java.awt.*;
import hsa.*;
public class CCC2005s5PinballRankingMerge
{
static Console c;
static double I;
public static void main (String[] args)
{
c = new Console ();
TextInputFile f = new TextInputFile ("s5.9.in");
I = 0;
int[] a = new int [100001];
int n;
n = f.readInt ();
for (int x = 0 ; x < n ; x++)
a [x] = f.readInt ();
mergeSort (a, 0, n - 1);
c.println ((I + n) / n, 0, 2);
}
// this is an inclusive a[x,z] merge sort
public static void mergeSort (int[] a, int x, int z)
{
if (x < z)
{
int y = (x + z) / 2;
mergeSort (a, x, y);
mergeSort (a, y + 1, z);
I += merge (a, x, y, z);
}
}
public static double merge (int[] a, int x, int y, int z)
{
int[] newa = new int [z - x + 1];
int xx = x;
int yy = y + 1;
int k = 0;
double total = 0;
while (xx <= y && yy <= z)
if (a [xx] <= a [yy])
newa [k++] = a [xx++];
else
{
newa [k++] = a [yy++];
total = total + (y + 1 - xx);
}
while (xx <= y)
newa [k++] = a [xx++];
while (yy <= z)
newa [k++] = a [yy++];
for (xx = x ; xx <= z ; xx++)
a [xx] = newa [xx - x];
return total;
}
}