CF846F Random Query

给定一个由 $n$ 个正整数组成的数组 $a$。你需要随机等概率独立地从 $1$ 到 $n$ 中各选一个整数 $l$ 和 $r$，如果 $l > r$，则交换 $l$ 和 $r$ 的值。请你计算，从下标 $l$ 到下标 $r$（包含两端，$1$ 为下标起点）所组成的区间内不同元素的个数的期望值。

第一行包含一个整数 $n$，满足 $1 \leq n \leq 10^{6}$。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示数组的各元素，满足 $1 \leq a_i \leq 10^{6}$。

输出一个数，表示所选区间内不同元素个数的期望值。 你的答案若与标准答案的绝对误差或相对误差不超过 $10^{-4}$，即认为正确。形式化地说，若 $|x - y| \le 10^{-4} \max(1, |x|)$，其中 $x$ 为标准答案，$y$ 为你的答案，则判为正确。

由 ChatGPT 5 翻译