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;
struct DO {
  vector<long long> do_arr;
  long long len;
  DO(vector<pair<long long, long long>> &a) {
    long long q1 = 1;
    while (q1 < a.size()) {
      q1 *= 2;
    }
    len = q1;
    for (long long q = 0; q < q1 * 2; q++) {
      do_arr.push_back(0);
    }
  }
  void change(long long q, long long x) {
    do_arr[q + len] = x;
    q = (q + len) / 2;
    while (q > 0) {
      do_arr[q] = do_arr[2 * q] + do_arr[2 * q + 1];
      q /= 2;
    }
  }
  long long ans(long long l, long long r, long long l1, long long r1,
                long long q) {
    if (r <= l1 || r1 <= l) {
      return 0;
    }
    if (l1 <= l && r <= r1) {
      return do_arr[q];
    }
    long long m = (l + r) / 2;
    return ans(l, m, l1, r1, 2 * q) + ans(m, r, l1, r1, 2 * q + 1);
  }
};
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long n;
  cin >> n;
  long long a[n];
  for (long long q = 0; q < n; q++) {
    cin >> a[q];
  }
  vector<pair<long long, long long>> d, d1;
  vector<pair<pair<long long, long long>, pair<long long, long long>>> s;
  unordered_map<long long, long long> was;
  for (long long q = 0; q < n; q++) {
    if (was.find(a[q]) != was.end()) {
      long long w = was[a[q]];
      s.push_back({{w, q}, {-1, -1}});
      d.push_back({min(w, n - q - 1) + q - w + 1, s.size() - 1});
      d1.push_back({n - min(w, n - q - 1), s.size() - 1});
      was[a[q]] = q;
    } else {
      was[a[q]] = q;
    }
  }
  sort(d.begin(), d.end());
  sort(d1.begin(), d1.end());
  for (long long q = 0; q < d.size(); q++) {
    s[d[q].second].second.first = q;
    s[d1[q].second].second.second = q;
  }
  long long OPKP = 0;
  sort(s.begin(), s.end(),
       [](pair<pair<long long, long long>, pair<long long, long long>> x,
          pair<pair<long long, long long>, pair<long long, long long>> y) {
         return x.first.second - x.first.first < y.first.second - y.first.first;
       });
  DO do_arr = *(new DO(d)), do_arr1 = *(new DO(d1));
  long long q1 = 0, ans = 0, q2 = 0, q3 = 0;
  for (long long q = 1; q < n + 1; q++) {
    while (q1 < s.size() && s[q1].first.second - s[q1].first.first == q - 1) {
      do_arr.change(s[q1].second.first, 1);
      do_arr1.change(s[q1].second.second, 1);
      q1++;
    }
    while (q2 < d.size() && d[q2].first < q) {
      q2++;
    }
    while (q3 < d1.size() && d1[q3].first < q) {
      q3++;
    }
    ans += do_arr.ans(0, do_arr.len, q2, n, 1) -
           do_arr1.ans(0, do_arr.len, 0, q3, 1);
    OPKP += q * (n - q + 1) - ans;
  }
  OPKP += OPKP - n;
  long long g = n * n;
  cout << fixed;
  cout << 1.0 * OPKP / g << '\n';
  return 0;
}