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;
using namespace chrono;
int advceil(int num, int den) {
  return (num % den == 0 ? num / den : num / den + 1);
}
int lstbt(int val) {
  int msk = val & (val - 1);
  return log2(val ^ msk);
}
int modmul(int a, int b) {
  if (a < 1e9 and b < 1e9) return (a * b) % 1000000007;
  a %= 1000000007;
  b %= 1000000007;
  int res = 0;
  while (b > 0) {
    if (b & 1) res = (res + a) % 1000000007;
    a = (a * 2) % 1000000007;
    b /= 2;
  }
  return res;
}
int modexpo(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = modmul(res, a);
    a = modmul(a, a);
    b /= 2;
  }
  return res;
}
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
vector<int> CALCfactor(int n) {
  vector<int> factor(n + 2, 0);
  for (int i = 4; i <= n; i += 2) factor[i] = 2;
  for (int j = 3; j <= n; j += 2) {
    if (factor[j]) continue;
    for (int i = 2 * j; i <= n; i += j) factor[i] = j;
  }
  return factor;
}
vector<int> CALCprimeNUM(int n) {
  vector<int> factor = CALCfactor(n);
  vector<int> primeNUM;
  primeNUM.reserve(n + 2);
  for (long long int i = 2; i <= n; i++)
    if (!factor[i]) primeNUM.push_back(i);
  return primeNUM;
}
vector<int> CALCprimeFACTOR(int n) {
  vector<int> factor = CALCfactor(n);
  vector<int> ans;
  while (factor[n] != 0) {
    ans.push_back(factor[n]);
    n /= factor[n];
  }
  if (n > 1) ans.push_back(n);
  return ans;
}
vector<int> unique(vector<int> x) {
  sort(x.begin(), x.end());
  set<int> s;
  vector<int> ans;
  ans.reserve(x.size());
  for (auto elem : x) s.insert(elem);
  for (auto elem : s) ans.push_back(elem);
  return ans;
}
pair<vector<int>, vector<int> > getFact(int n) {
  vector<int> fact(n + 1, 1), invfact(n + 1, 1);
  for (long long int i = 1; i <= n; i++)
    fact[i] = (i * (fact[i - 1])) % 1000000007;
  for (long long int i = 1; i <= n; i++)
    invfact[i] = (modexpo(i, 1000000007 - 2) * invfact[i - 1]) % 1000000007;
  return {fact, invfact};
}
void compress(vector<int>& arr, int n) {
  map<int, vector<int> > pos;
  for (long long int i = 1; i <= n; i++) pos[arr[i]].push_back(i);
  int cnt = 1;
  for (auto itr : pos) {
    for (auto elem : itr.second) arr[elem] = cnt;
    cnt++;
  }
}
bool rcomp(int a, int b) { return a > b; }
long long int segment[100001 * 40 + 1] = {};
int lazy[100001 * 40 + 1] = {};
class segmentTree {
 private:
  long long int N, typ, BASE;
  long long int combine(long long int x, long long int y) {
    if (typ == 0)
      return x + y;
    else if (typ == 1)
      return min(x, y);
    else if (typ == 2)
      return max(x, y);
    return 0;
  }
  void call(long long int idx, long long int s, long long int e) {
    segment[idx] += (e - s + 1) * lazy[idx];
    if (s != e) {
      lazy[2 * idx] += lazy[idx];
      lazy[2 * idx + 1] += lazy[idx];
    }
    lazy[idx] = 0;
  }
  void update1(long long int s, long long int e, long long int l,
               long long int r, long long int idx, long long int val) {
    if (lazy[idx]) call(idx, s, e);
    if (e < l or r < s)
      return;
    else if (l <= s and e <= r) {
      lazy[idx] += val;
      call(idx, s, e);
      return;
    }
    long long int mid = (s + e) >> 1;
    update1(s, mid, l, r, 2 * idx, val);
    update1(mid + 1, e, l, r, 2 * idx + 1, val);
    segment[idx] = combine(segment[2 * idx], segment[2 * idx + 1]);
  }
  long long int query1(int s, int e, int l, int r, int idx) {
    if (lazy[idx]) call(idx, s, e);
    if (e < l or r < s)
      return BASE;
    else if (l <= s and e <= r) {
      return segment[idx];
    }
    long long int mid = (s + e) >> 1;
    long long int lt = query1(s, mid, l, r, 2 * idx);
    long long int rt = query1(mid + 1, e, l, r, 2 * idx + 1);
    return combine(lt, rt);
  }

 public:
  segmentTree(long long int n, long long int type) {
    N = n;
    typ = type;
    if (typ == 0)
      BASE = 0;
    else if (typ == 1)
      BASE = 1e9;
    else if (typ == 2)
      BASE = -1e9;
  }
  void update(long long int s, long long int e, long long int x) {
    if (s > e) return;
    update1(1, N, s, e, 1, x);
  }
  long long int query(long long int s, long long int e) {
    if (s > e) return 0ll;
    return query1(1, N, s, e, 1);
  }
};
vector<int> pos[100001 * 10];
map<int, int> spos;
void solve() {
  long long int n;
  cin >> n;
  vector<int> arr(n + 1, 0);
  for (long long int i = 1; i <= n; i++) cin >> arr[i];
  segmentTree st(n, 0);
  for (long long int i = 1; i <= n; i++) {
    spos[arr[i]]++;
    st.update(i, i, spos.size());
  }
  for (long long int i = n + 1 - 1; i >= 1; i--) pos[arr[i]].push_back(i);
  long long int sum = 0;
  for (long long int i = 1; i <= n; i++) {
    sum -= 1;
    sum += 2ll * st.query(i, n);
    st.update(i + 1, n, -1);
    pos[arr[i]].pop_back();
    if (pos[arr[i]].size()) {
      st.update(pos[arr[i]].back(), n, 1ll);
    }
  }
  cout << fixed << setprecision(8);
  long long int mynum = n;
  cout << (sum * 1.0 / (mynum * mynum)) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  auto start1 = high_resolution_clock::now();
  solve();
  auto stop1 = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop1 - start1);
}