其实，我们就是要求一个序列的所有子区间的数的种类数之和
我们考虑，假设从左到右第一次出现的数产生贡献
那么，对于一个数$a_i$，它产生贡献的区间
l 需要在 相同数的上一次出现的位置 + 1 ~ i
r 需要在 i~n
对于生成的l,r 有 $n^2$种情况
其中l ≠ r 时都有两种可能(l> r 和 l < r)
l = r时候只有一种情况
所以要特殊处理 l = r
```
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MAXN 1000005
LL n,m;
LL a[MAXN],c[MAXN];
LL ans;
void rd()
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
}
int main()
{
rd();
for(int i = 1; i <= n; i ++) {
ans += (i - c[a[i]]) * (n - i+1) * 2 - 2;
c[a[i]] = i;
}
ans += n;
printf("%.6lf",(double)ans/(double)(n*n));
return 0;
}
```