大样例下载

题目描述

一个序列 $A$ 含有 $n$ 个整数 $A_i$。

现在，你想让所有整数变成相同的。你可以进行以下操作，每次操作包含以下四步：

• 首先，从序列中任选一个整数 $A_x$

• 然后，从序列剩余元素中再任选一个整数 $A_y$

• 比较 $A_x$ 与 $A_y$，如果二者不同，则将 $A_y$ 变成 $A_x$

• 最后，将两个相同的整数放回原序列中。

重复以上操作，直到序列中所有元素均相同。

求期望操作次数？

输入

第一行：一个整数 $n$

第二行：包含 $n$ 个整数 $A_i$

输出

一个实数，表示结果，保留 $1$ 位小数。

样例1输入

3
1 1 1

样例1输出

0.0

样例2输入

3
1 2 3

样例2输出

4.0

数据范围

10% 的数据，$n ≤ 20$

40% 的数据，$n ≤ 200$

50% 的数据，$n ≤ 1000$

100% 的数据，$n ≤ 10000, 0 ≤ A_i ≤ 30$