Random Query

题意翻译

- 给定长度为 $n$ 的序列 $a$。您要随机地选取两个数 $l,r\in [1,n]$，如果 $l>r$，则交换 $l,r$。求 $a_l\sim a_r$ 中不同数字个数的期望。 - $1\le n\le 10^6$，$1\le a_i\le 10^6$。答案被认为是正确的当且仅当 $\min\left(|x-y|,\dfrac{|x-y|}{x}\right)\le 10^{-4}$，其中 $x$ 是标准答案，$y$ 是您的答案。

题目描述

You are given an array $ a $ consisting of $ n $ positive integers. You pick two integer numbers $ l $ and $ r $ from $ 1 $ to $ n $ , inclusive (numbers are picked randomly, equiprobably and independently). If $ l>r $ , then you swap values of $ l $ and $ r $ . You have to calculate the expected value of the number of unique elements in segment of the array from index $ l $ to index $ r $ , inclusive ( $ 1 $ -indexed).

输入输出格式

输入格式

The first line contains one integer number $ n $ $ (1<=n<=10^{6}) $ . The second line contains $ n $ integer numbers $ a_{1} $ , $ a_{2} $ , ... $ a_{n} $ $ (1<=a_{i}<=10^{6}) $ — elements of the array.

输出格式

Print one number — the expected number of unique elements in chosen segment. Your answer will be considered correct if its absolute or relative error doesn't exceed $ 10^{-4} $ — formally, the answer is correct if , where $ x $ is jury's answer, and $ y $ is your answer.

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

1.500000

输入样例 #2

2
2 2

输出样例 #2

1.000000