CF846F.Random Query

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).

给你一个由 $n$ 个正整数组成的数组 $a$。你从 $1$ 到 $n$（含）中随机、等概率且独立地选取两个整数 $l$ 和 $r$。若 $l > r$，则交换 $l$ 和 $r$ 的值。你需要计算数组中从索引 $l$ 到索引 $r$（含，1-索引）这一区间内不同元素个数的期望值。

The first line contains one integer number n (1 ≤ n ≤ 106). The second line contains n integer numbers _a_1, _a_2, ... a__n (1 ≤ a__i ≤ 106) — elements of the array.

第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^6 $）。
第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq 10^6 $）—— 数组的元素。

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.

输出一个数字——所选区间中不同元素的期望数量。

若您的答案的绝对或相对误差不超过 $10^{-4}$，则视为正确。形式化地说，当且仅当 时，答案正确，其中 $x$ 是出题方的答案，$y$ 是您的答案。