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>
#pragma GCC optimize("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}
template <class V, int NV>
struct LazySegTree {
  vector<V> dat, lazy;
  LazySegTree() {
    dat.resize(NV * 2, def);
    lazy.resize(NV * 2, ldef);
  }
  void update(int a, int b, V v, int k, int l, int r) {
    push(k, l, r);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      setLazy(k, v);
      push(k, l, r);
    } else {
      update(a, b, v, k * 2 + 1, l, (l + r) / 2);
      update(a, b, v, k * 2 + 2, (l + r) / 2, r);
      dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  V get(int a, int b, int k, int l, int r) {
    push(k, l, r);
    if (r <= a || b <= l) return def;
    if (a <= l && r <= b) return dat[k];
    auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
    auto y = get(a, b, k * 2 + 2, (l + r) / 2, r);
    return comp(x, y);
  }
  void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); }
  V get(int a, int b) { return get(a, b, 0, 0, NV); }
  const V def = 0, ldef = 0;
  V comp(V l, V r) { return l + r; }
  void setLazy(int i, V v) { lazy[i] += v; }
  void push(int k, int l, int r) {
    dat[k] += lazy[k] * (r - l);
    if (r - l > 1) {
      setLazy(k * 2 + 1, lazy[k]);
      setLazy(k * 2 + 2, lazy[k]);
    }
    lazy[k] = ldef;
  }
};
int N, A[1010101];
LazySegTree<long long, 1 << 20> lst;
int pre[1010101];
void _main() {
  cin >> N;
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < 1010101; i++) pre[i] = -1;
  long long sm = 0;
  for (int i = 0; i < N; i++) {
    lst.update(pre[A[i]] + 1, i + 1, 1);
    sm += lst.get(0, i + 1);
    sm += lst.get(0, i);
    pre[A[i]] = i;
  }
  double up = sm;
  double dow = 1.0 * N * N;
  double ans = up / dow;
  printf("%.10f\n", ans);
}