给定一个由 n 个正整数组成的数组 a。您从 1 到 n(含)中选择两个整数 l 和 r(数字是随机、等概率且独立地选择的)。如果 l > r,则交换 l 和 r 的值。您必须计算从索引 l 到索引 r(包括索引 1)的数组段中唯一元素数量的预期值。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106)。第二行包含 n 个整数 a1, a2, ... an (1 ≤ ai ≤ 106) — 数组的元素。
输出
打印一个数字 — 所选段中唯一元素的预期数量。
如果绝对或相对误差不超过 10 - 4,则您的答案将被视为正确 — 正式来说,如果 $${ \operatorname* { m i n } } ( | x - y |, { \frac { | x - y | } { x } } ) \leq 1 0 ^ { - 4 }$$,则答案是正确的,其中 x 是陪审团的答案,y 是您的答案回答。
示例
输入 #1
2 1 2
输出 #1
1.500000
输入 #2
2 2 2
输出 #2
1.000000