#include <bits/stdc++.h>
using namespace std;
struct node {
  int val;
  node *left, *right;
  node(int v, node *L = NULL, node *R = NULL) : val(v), left(L), right(R) {}
};
const int MAXN = 1000010;
node *arb[MAXN];
int N, L, U;
map<int, int> lastPos;
inline int val(node *n) { return n ? n->val : 0; }
inline node *leftChild(node *n) { return n ? n->left : NULL; }
inline node *rightChild(node *n) { return n ? n->right : NULL; }
node *insert(node *root, int pos, int v, int left, int right) {
  if (left == right) return new node(v);
  if (left > right) return NULL;
  int mid = left + (right - left) / 2;
  if (pos <= mid) {
    node *t = insert(leftChild(root), pos, v, left, mid);
    return new node(val(t) + val(rightChild(root)), t, rightChild(root));
  } else {
    node *t = insert(rightChild(root), pos, v, mid + 1, right);
    return new node(val(leftChild(root)) + val(t), leftChild(root), t);
  }
}
int qL, qR;
int _query(node *root, int left, int right) {
  if (right < qL || left > qR) return 0;
  if (qL <= left && right <= qR) return val(root);
  int mid = left + (right - left) / 2;
  return _query(leftChild(root), left, mid) +
         _query(rightChild(root), mid + 1, right);
}
int query(node *root, int left, int right) {
  qL = left, qR = right;
  return _query(root, 1, N);
}
int binSrch(int r, int k) {
  int left = 1, right = r;
  int found = 0;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    int d = query(arb[r], mid, r);
    if (d >= k) {
      if (d == k) found = mid;
      left = mid + 1;
    } else
      right = mid - 1;
  }
  return found;
}
int main() {
  arb[0] = NULL;
  long long ans = 0;
  scanf("%d", &N);
  long long prv = 0;
  for (int i = 1; i <= N; ++i) {
    int a;
    scanf("%d", &a);
    int lp = lastPos[a];
    ans += 1LL * 2 * (prv + i - lp) - 1;
    prv = prv + i - lp;
    lastPos[a] = i;
  }
  lastPos.clear();
  printf("%.8lf\n", (double)ans / (1LL * N * N));
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct node {
  int val;
  node *left, *right;
  node(int v, node *L = NULL, node *R = NULL) : val(v), left(L), right(R) {}
};
const int MAXN = 1000010;
node *arb[MAXN];
int N, L, U;
map<int, int> lastPos;
inline int val(node *n) { return n ? n->val : 0; }
inline node *leftChild(node *n) { return n ? n->left : NULL; }
inline node *rightChild(node *n) { return n ? n->right : NULL; }
node *insert(node *root, int pos, int v, int left, int right) {
  if (left == right) return new node(v);
  if (left > right) return NULL;
  int mid = left + (right - left) / 2;
  if (pos <= mid) {
    node *t = insert(leftChild(root), pos, v, left, mid);
    return new node(val(t) + val(rightChild(root)), t, rightChild(root));
  } else {
    node *t = insert(rightChild(root), pos, v, mid + 1, right);
    return new node(val(leftChild(root)) + val(t), leftChild(root), t);
  }
}
int qL, qR;
int _query(node *root, int left, int right) {
  if (right < qL || left > qR) return 0;
  if (qL <= left && right <= qR) return val(root);
  int mid = left + (right - left) / 2;
  return _query(leftChild(root), left, mid) +
         _query(rightChild(root), mid + 1, right);
}
int query(node *root, int left, int right) {
  qL = left, qR = right;
  return _query(root, 1, N);
}
int binSrch(int r, int k) {
  int left = 1, right = r;
  int found = 0;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    int d = query(arb[r], mid, r);
    if (d >= k) {
      if (d == k) found = mid;
      left = mid + 1;
    } else
      right = mid - 1;
  }
  return found;
}
int main() {
  arb[0] = NULL;
  long long ans = 0;
  scanf("%d", &N);
  long long prv = 0;
  for (int i = 1; i <= N; ++i) {
    int a;
    scanf("%d", &a);
    int lp = lastPos[a];
    ans += 1LL * 2 * (prv + i - lp) - 1;
    prv = prv + i - lp;
    lastPos[a] = i;
  }
  lastPos.clear();
  printf("%.8lf\n", (double)ans / (1LL * N * N));
  return 0;
}

```