← 返回题目

题库练习 Random Query

← 上一题下一题 →

A11100 | $Random Query$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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 ![](/uploads/acgo/image/a65b1f931e20a205_b1910ff96cb1.jpeg), 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

C++ 编辑器

输入

输出