题目描述

友爱的 YY 小朋友,正在学习快速排序，聪明的他很快就发现，快排是会出现退化的情况的。

于是乎他友爱地发明了用随机化的方法。

但是这个时候友爱的小 YY 还是不满足于现状，他想知道怎么证明快速排序的期望复杂度是 $\text{O}(n\ log n)$。

于是他决定自己定义代价自己算，他的快速排序过程是这样的：

首先在待排序的数字里随机选取一个 $X$ 作为基准点,然后代价变量 $S=$ 划分代价（划分代价即在 $X$ 的左边比 $X$ 大的数字的个数 + 在 $X$ 的右边比 $X$ 小的数字的个数）+ 将两部分分别递归下去的 $S$。

注意：划分的过程中保持相对位置不变。

聪明又友爱的他很快就发现 $S$ 的最大期望是 $\text{O}(n\log n)$ 的级别的，但是好学的他还想知道对于一个具体的，数字不重复的序列，$S$ 的期望是多少。当然你要知道 YY 是要拿 UOI 金牌的人，所以他决定让你来完成计算的工作。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数，表示待排序数列（每个数字均在 int 范围内）。

输出格式

一个实数，$S$ 的期望值。（保留六位小数）

3
1 2 3

0.000000

数据规模与约定

对于 $20\%$ 的数据，$1\le n\le 300$。
对于 $100\%$ 的数据，$1\leq n\leq 1.5\times 10^4$。