← 返回题目列表

Codeforces · 846/F

F. 随机查询

中文机器翻译题面 查看原题

给定一个由 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