Average Reduction in Dream's Second Music Disk Selection

Dream has (n) music disks numbered from (1) to (n). Each disk (i) stores one song represented by a positive integer (a_i) with (1\le a_i\le n).

Initially, Dream chooses two non‐empty intervals uniformly at random: an index interval (P_1=[l_p,r_p]) from ([1,n]) and a song interval (S_1=[l_s,r_s]) from ([1,n]). He then picks as many disks as possible from (P_1) whose song values lie in (S_1), under the constraint that no two selected disks have the same song. In other words, he picks a set of disks whose size is equal to the number of distinct song values in ({ a_i : i\in P_1} \cap S_1).

Not satisfied with the quantity, Dream performs a second selection. He again randomly (and uniformly) chooses two non‐empty intervals (P_2) and (S_2) such that (P_2\subseteq P_1) and (S_2\subseteq S_1). Now he picks the maximum set of disks from (P_2) whose song values lie in (S_2) (again, all songs must be distinct).

Tommy feels that Dream has given him too few disks. Your task is to compute the average decrease in the set size caused by the second selection, i.e. the average value of (\Delta = X_1 - X_2) taken over all choices of the intervals (P_1, S_1, P_2, S_2).

For a fixed (P_1=[l_p,r_p]) and (S_1=[l_s,r_s]):
(X_1) is the number of integers (s) in (S_1) such that there exists an index (i\in P_1) with (a_i=s).
For each such song (s), let
(p_{P}(s) = \frac{\text{# subintervals of }P_1 \text{ that contain at least one occurrence of }s}{\frac{|P_1|(|P_1|+1)}{2}}), and
(p_{S}(s) = \frac{(s - l_s + 1)\cdot(r_s - s + 1)}{\frac{|S_1|(|S_1|+1)}{2}}),
so that the probability that (s) appears in the second selection is (p_{P}(s)\cdot p_{S}(s)).
Then the expected distinct count in the second selection is (X_2 = \sum_{s\in S_1 \text{ and } s \text{ occurs in }P_1}, p_{P}(s), p_{S}(s)), and the reduction is (X_1 - X_2).

The overall average reduction is taken over all possible choices of (P_1) and (S_1) (which are non-empty intervals of ([1,n])), with the subsequent (P_2,S_2) chosen uniformly among all non-empty subintervals of (P_1) and (S_1), respectively.

You are given (n) and the array (a), and you should output the average reduction (as a floating-point number) caused by the second selection.

Note: All formulas are written in (\LaTeX) format.

inputFormat

The first line contains a single integer (n) (the number of disks).

The second line contains (n) integers (a_1, a_2, \ldots, a_n) representing the song value stored in each disk.

outputFormat

Output a single floating-point number representing the average reduction (\Delta = X_1 - X_2) due to the second selection. It is recommended to print the result with at least 6 decimal places.

sample

1
1

0.000000