安德鲁和杰瑞正在玩一场游戏,哈利担任记分员。比赛分为三轮。在每一轮中,安德鲁和杰瑞从一个装有 n 个球的罐子中随机抽取,没有放回,每个球都标有不同的正整数。他们看也不看,就把球递给哈利,哈利将分数奖励给数字较大的玩家,并将球放回罐子里。比赛的获胜者是三轮中至少赢得两轮的一方。
Andrew 赢得了第 1 轮和第 2 轮,而 Jerry 赢得了第 3 轮,因此 Andrew 赢得了比赛。然而,杰里对这种制度并不满意,声称尽管总分较高,但他经常会输掉比赛。杰瑞抽到的三个球的总和严格高于安德鲁抽到的三个球的总和的概率是多少?
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 2000) — 罐子中球的数量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 5000) — 第 i 个球上写的数字。保证没有两个球具有相同的数字。
输出
打印一个实际值 - 考虑到安德鲁赢得前两轮而杰瑞赢得第三轮,杰瑞拥有更高总数的概率。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
2 1 2
输出 #1
0.0000000000
输入 #2
3 1 2 10
输出 #2
0.0740740741
注意
在第一种情况下,只有两个球。在前两轮中,安德鲁必须抽到 2,而杰瑞必须抽到 1,最后一轮则相反。因此,Andrew 的总和为 5,而 Jerry 的总和为 4,因此 Jerry 的总和从未更高。
在第二种情况下,每场比赛可能有三种结果 - 10 - 2、10 - 1 或 2 - 1。当且仅当安德鲁在前两轮都以 2 - 1 获胜,并且杰里在最后一轮抽到 10 时,杰瑞的总分更高。其概率为 $$\frac{1}{3} \cdot \frac{1}{3} \cdot \frac{2}{3} = \frac{2}{27}$$。