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

Input

The first line contains one integer number n (1 ≤ n ≤ 106). The second line contains n integer numbers a1, a2, ... an (1 ≤ ai ≤ 106) — elements of the array.

Output

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 <image>, where x is jury's answer, and y is your answer.

Examples

Input

2
1 2


Output

1.500000


Input

2
2 2


Output

1.000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
long long add(long long a, long long b, long long m = 1000000007) {
  long long ret = a + b;
  if (ret >= m) ret -= m;
  return ret;
}
long long subtract(long long a, long long b, long long m = 1000000007) {
  long long ret = a - b;
  if (ret < 0) ret += m;
  return ret;
}
long long mult(long long a, long long b, long long m = 1000000007) {
  long long ret = a * b;
  if (ret >= m) ret %= m;
  return ret;
}
long long bigmod(long long a, long long b, long long m = 1000000007) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = mult(ret, a, m);
    b >>= 1;
    a = mult(a, a, m);
  }
  return ret;
}
long long inverse(long long n, long long m = 1000000007) {
  return bigmod(n, 1000000007 - 2, m);
}
long long tree[1000010 * 4], lazy[1000010 * 4];
void update_node(int node, int l, int h, int val) {
  tree[node] += val * (h - l + 1);
  lazy[node] += val;
}
void push(int node, int l, int h) {
  if (lazy[node]) {
    int m = (l + h) / 2;
    update_node((node << 1), l, m, lazy[node]);
    update_node(((node << 1) | 1), m + 1, h, lazy[node]);
    lazy[node] = 0;
  }
}
void update(int node, int l, int h, int i, int j, int val) {
  if (l > h || i > j) return;
  if (i == l && j == h) {
    update_node(node, l, h, val);
    return;
  }
  push(node, l, h);
  int m = (l + h) / 2;
  if (j <= m)
    update((node << 1), l, m, i, j, val);
  else if (i > m)
    update(((node << 1) | 1), m + 1, h, i, j, val);
  else {
    update((node << 1), l, m, i, m, val);
    update(((node << 1) | 1), m + 1, h, m + 1, j, val);
  }
  tree[node] = tree[(node << 1)] + tree[((node << 1) | 1)];
}
long long query(int node, int l, int h, int i, int j) {
  if (l > h || i > j) return 0;
  if (i == l && j == h) return tree[node];
  push(node, l, h);
  int m = (l + h) / 2;
  if (j <= m)
    return query((node << 1), l, m, i, j);
  else if (i > m)
    return query(((node << 1) | 1), m + 1, h, i, j);
  return query((node << 1), l, m, i, m) +
         query(((node << 1) | 1), m + 1, h, m + 1, j);
}
int a[1000010], vis[1000010];
vector<int> nxt[1000010];
long long bruteforce(int n) {
  long long ret = 0;
  for (int i = 0; i < n; ++i) {
    int cnt = 1;
    for (int j = 0; j < n; ++j) vis[a[j]] = 0;
    vis[a[i]] = 1;
    for (int j = i + 1; j < n; ++j) {
      if (vis[a[j]] == 0) ++cnt;
      vis[a[j]] = 1;
      ret += cnt;
    };
  }
  return ret * 2 + n;
}
int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
      nxt[a[i]].push_back(i);
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (vis[a[i]] == 0) ++cnt;
      vis[a[i]] = 1;
      update(1, 0, n - 1, i, i, cnt);
    }
    long long ans = query(1, 0, n - 1, 1, n - 1);
    for (int i = 1; i < n; ++i) {
      int id = n;
      auto it = lower_bound(nxt[a[i - 1]].begin(), nxt[a[i - 1]].end(), i);
      if (it != nxt[a[i - 1]].end()) id = *it;
      update(1, 0, n - 1, i, id - 1, -1);
      ans += query(1, 0, n - 1, i + 1, n - 1);
    }
    ans *= 2;
    ans += n;
    printf("%.10lf\n", 1.0 * ans / n / n);
    for (int i = 0; i < 1000010; ++i) nxt[i].clear();
    memset(tree, 0, sizeof(tree));
    memset(lazy, 0, sizeof(lazy));
    memset(vis, 0, sizeof(vis));
  }
  return 0;
}