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;
long long seg[10000000], a[1000111], next1[1000110], final[1000110], n,
    b[1000110], lazy[10000001];
void build(int node, int start, int end) {
  if (start == end) {
    seg[node] = b[start];
  } else {
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    seg[node] = seg[2 * node] + seg[2 * node + 1];
  }
}
void update(int node, int start, int end, int l, int r, long long val) {
  if (lazy[node] != 0) {
    seg[node] += (end - start + 1) * lazy[node];
    if (start != end) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
  if (start > end || start > r || end < l) return;
  if (start >= l && end <= r) {
    seg[node] += (end - start + 1) * val;
    if (start != end) {
      lazy[node * 2] += val;
      lazy[node * 2 + 1] += val;
    }
    return;
  }
  int mid = (start + end) / 2;
  update(node * 2, start, mid, l, r, val);
  update(node * 2 + 1, mid + 1, end, l, r, val);
  seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
long long sum(int node, int start, int end, int l, int r) {
  if (start > end || start > r || end < l) return 0;
  if (lazy[node] != 0) {
    seg[node] += (end - start + 1) * lazy[node];
    if (start != end) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
  if (start >= l && end <= r) return seg[node];
  int mid = (start + end) / 2;
  long long p1 = sum(node * 2, start, mid, l, r);
  long long p2 = sum(node * 2 + 1, mid + 1, end, l, r);
  return (p1 + p2);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    final[a[i]] = i;
    next1[i] = n;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (i != final[a[i]]) {
      next1[i] = final[a[i]];
    }
    final[a[i]] = i;
  }
  for (int i = 0; i <= 1000009; i++) final[i] = 0;
  long long have = 0;
  for (int i = 0; i < n; i++) {
    if (final[a[i]] == 0) have++, final[a[i]] = 1;
    b[i] = have;
  }
  build(1, 0, n - 1);
  double ans = 0;
  for (int i = 0; i < n; i++) {
    ans += (double)(sum(1, 0, n - 1, i, n - 1)) / (double)(n * n);
    update(1, 0, n - 1, i, next1[i] - 1, -1);
  }
  ans *= 2;
  ans -= (double)1 / n;
  printf("%.9f", ans);
}