#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n, a[MAXN], nxt[MAXN], pos[MAXN], b[MAXN];
bool vis[MAXN];
long long sum[MAXN << 2];
int lazy[MAXN << 2];
void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void PushDown(int rt, int m) {
  if (lazy[rt] != 0) {
    sum[rt << 1] += (m - (m >> 1)) * lazy[rt];
    sum[rt << 1 | 1] += (m >> 1) * lazy[rt];
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt] = 0;
  }
}
void Build(int l, int r, int rt) {
  sum[rt] = lazy[rt] = 0;
  if (l == r) {
    sum[rt] = b[l];
    return;
  }
  int mid = (l + r) >> 1;
  Build(l, mid, rt << 1);
  Build(mid + 1, r, rt << 1 | 1);
  PushUp(rt);
}
void UpDate(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    sum[rt] += (r - l + 1) * -1;
    lazy[rt] -= 1;
    return;
  }
  PushDown(rt, r - l + 1);
  int mid = (l + r) >> 1;
  if (L <= mid) UpDate(L, R, l, mid, rt << 1);
  if (R > mid) UpDate(L, R, mid + 1, r, rt << 1 | 1);
  PushUp(rt);
}
long long Query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return sum[rt];
  }
  PushDown(rt, r - l + 1);
  int mid = (l + r) >> 1;
  long long ret = 0;
  if (L <= mid) ret += Query(L, R, l, mid, rt << 1);
  if (R > mid) ret += Query(L, R, mid + 1, r, rt << 1 | 1);
  PushUp(rt);
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memset(pos, -1, sizeof(pos));
  for (int i = n; i >= 1; i--) {
    if (pos[a[i]] == -1)
      nxt[i] = n + 1;
    else
      nxt[i] = pos[a[i]];
    pos[a[i]] = i;
  }
  b[0] = 0;
  memset(vis, false, sizeof(vis));
  for (int i = 1; i <= n; i++) {
    b[i] = b[i - 1];
    if (!vis[a[i]]) b[i]++;
    vis[a[i]] = true;
  }
  Build(1, n, 1);
  long long ans = sum[1] * 2 - b[1];
  for (int i = 1; i < n; i++) {
    UpDate(i + 1, nxt[i] - 1, 1, n, 1);
    ans += Query(i + 1, n, 1, n, 1) * 2 - Query(i + 1, i + 1, 1, n, 1);
  }
  double N = 1.0 * n * n;
  double Ans = 1.0 * ans / N;
  printf("%.8f\n", Ans);
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
const int MAXN = 1e6 + 5;
int n, a[MAXN], nxt[MAXN], pos[MAXN], b[MAXN];
bool vis[MAXN];
long long sum[MAXN << 2];
int lazy[MAXN << 2];
void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void PushDown(int rt, int m) {
  if (lazy[rt] != 0) {
    sum[rt << 1] += (m - (m >> 1)) * lazy[rt];
    sum[rt << 1 | 1] += (m >> 1) * lazy[rt];
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt] = 0;
  }
}
void Build(int l, int r, int rt) {
  sum[rt] = lazy[rt] = 0;
  if (l == r) {
    sum[rt] = b[l];
    return;
  }
  int mid = (l + r) >> 1;
  Build(l, mid, rt << 1);
  Build(mid + 1, r, rt << 1 | 1);
  PushUp(rt);
}
void UpDate(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    sum[rt] += (r - l + 1) * -1;
    lazy[rt] -= 1;
    return;
  }
  PushDown(rt, r - l + 1);
  int mid = (l + r) >> 1;
  if (L <= mid) UpDate(L, R, l, mid, rt << 1);
  if (R > mid) UpDate(L, R, mid + 1, r, rt << 1 | 1);
  PushUp(rt);
}
long long Query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return sum[rt];
  }
  PushDown(rt, r - l + 1);
  int mid = (l + r) >> 1;
  long long ret = 0;
  if (L <= mid) ret += Query(L, R, l, mid, rt << 1);
  if (R > mid) ret += Query(L, R, mid + 1, r, rt << 1 | 1);
  PushUp(rt);
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memset(pos, -1, sizeof(pos));
  for (int i = n; i >= 1; i--) {
    if (pos[a[i]] == -1)
      nxt[i] = n + 1;
    else
      nxt[i] = pos[a[i]];
    pos[a[i]] = i;
  }
  b[0] = 0;
  memset(vis, false, sizeof(vis));
  for (int i = 1; i <= n; i++) {
    b[i] = b[i - 1];
    if (!vis[a[i]]) b[i]++;
    vis[a[i]] = true;
  }
  Build(1, n, 1);
  long long ans = sum[1] * 2 - b[1];
  for (int i = 1; i < n; i++) {
    UpDate(i + 1, nxt[i] - 1, 1, n, 1);
    ans += Query(i + 1, n, 1, n, 1) * 2 - Query(i + 1, i + 1, 1, n, 1);
  }
  double N = 1.0 * n * n;
  double Ans = 1.0 * ans / N;
  printf("%.8f\n", Ans);
}

```