#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& s, pair<T, long long int> a) {
  s << a.first << ' ' << a.second;
  return s;
}
long long int st[4 * 1000005];
int lz[4 * 1000005];
int ara[1000005];
long long int f(long long int l, long long int r) { return l + r; }
void propagate(int node, int ss, int sf) {
  if (lz[node] == 0) return;
  st[node] += (long long int)(sf - ss + 1) * lz[node];
  if (ss != sf) {
    lz[2 * node] += lz[node];
    lz[2 * node + 1] += lz[node];
  }
  lz[node] = 0;
}
void init(int node, int ss, int sf) {
  if (ss == sf) {
    st[node] = ara[ss];
    return;
  }
  int mid = (ss + sf) / 2;
  init(2 * node, ss, mid);
  init(2 * node + 1, mid + 1, sf);
  st[node] = f(st[2 * node], st[2 * node + 1]);
}
void update(int node, int ss, int sf, int qs, int qe, int val) {
  propagate(node, ss, sf);
  if (qs > sf || qe < ss || sf < ss) return;
  if (qs <= ss && qe >= sf) {
    lz[node] += val;
    propagate(node, ss, sf);
    return;
  }
  int mid = (ss + sf) / 2;
  update(2 * node, ss, mid, qs, qe, val);
  update(2 * node + 1, mid + 1, sf, qs, qe, val);
  st[node] = f(st[2 * node], st[2 * node + 1]);
}
long long int query(int node, int ss, int sf, int qs, int qe) {
  propagate(node, ss, sf);
  if (qs > sf || qe < ss || sf < ss) return 0;
  if (qs <= ss && qe >= sf) return st[node];
  long long int mid = (ss + sf) / 2;
  return f(query(2 * node, ss, mid, qs, qe),
           query(2 * node + 1, mid + 1, sf, qs, qe));
}
vector<int> last[1000005];
int v[1000005];
int cnt[1000005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  for (int qq = 1; qq <= T; qq++) {
    long long int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> v[i];
    last[v[0]].push_back(0);
    long long int u = 1;
    ara[0] = 1;
    for (int i = 1; i < n; i++) {
      last[v[i]].push_back(i);
      if (last[v[i]].size() == 1) u++;
      ara[i] = u;
    }
    init(1, 0, n - 1);
    double ans = 2 * query(1, 0, n - 1, 0, n - 1);
    cnt[v[0]]++;
    for (int i = 1; i < n; i++) {
      long long int x = n - 1;
      if (last[v[i - 1]].size() != cnt[v[i - 1]])
        x = last[v[i - 1]][cnt[v[i - 1]]] - 1;
      cnt[v[i]]++;
      update(1, 0, n - 1, i - 1, x, -1);
      ans += 2 * query(1, 0, n - 1, 0, n - 1);
    }
    ans -= n;
    ans /= (1LL * n * n);
    cout << fixed << setprecision(10) << ans << endl;
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
template <class T>
ostream& operator<<(ostream& s, pair<T, long long int> a) {
  s << a.first << ' ' << a.second;
  return s;
}
long long int st[4 * 1000005];
int lz[4 * 1000005];
int ara[1000005];
long long int f(long long int l, long long int r) { return l + r; }
void propagate(int node, int ss, int sf) {
  if (lz[node] == 0) return;
  st[node] += (long long int)(sf - ss + 1) * lz[node];
  if (ss != sf) {
    lz[2 * node] += lz[node];
    lz[2 * node + 1] += lz[node];
  }
  lz[node] = 0;
}
void init(int node, int ss, int sf) {
  if (ss == sf) {
    st[node] = ara[ss];
    return;
  }
  int mid = (ss + sf) / 2;
  init(2 * node, ss, mid);
  init(2 * node + 1, mid + 1, sf);
  st[node] = f(st[2 * node], st[2 * node + 1]);
}
void update(int node, int ss, int sf, int qs, int qe, int val) {
  propagate(node, ss, sf);
  if (qs > sf || qe < ss || sf < ss) return;
  if (qs <= ss && qe >= sf) {
    lz[node] += val;
    propagate(node, ss, sf);
    return;
  }
  int mid = (ss + sf) / 2;
  update(2 * node, ss, mid, qs, qe, val);
  update(2 * node + 1, mid + 1, sf, qs, qe, val);
  st[node] = f(st[2 * node], st[2 * node + 1]);
}
long long int query(int node, int ss, int sf, int qs, int qe) {
  propagate(node, ss, sf);
  if (qs > sf || qe < ss || sf < ss) return 0;
  if (qs <= ss && qe >= sf) return st[node];
  long long int mid = (ss + sf) / 2;
  return f(query(2 * node, ss, mid, qs, qe),
           query(2 * node + 1, mid + 1, sf, qs, qe));
}
vector<int> last[1000005];
int v[1000005];
int cnt[1000005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  for (int qq = 1; qq <= T; qq++) {
    long long int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> v[i];
    last[v[0]].push_back(0);
    long long int u = 1;
    ara[0] = 1;
    for (int i = 1; i < n; i++) {
      last[v[i]].push_back(i);
      if (last[v[i]].size() == 1) u++;
      ara[i] = u;
    }
    init(1, 0, n - 1);
    double ans = 2 * query(1, 0, n - 1, 0, n - 1);
    cnt[v[0]]++;
    for (int i = 1; i < n; i++) {
      long long int x = n - 1;
      if (last[v[i - 1]].size() != cnt[v[i - 1]])
        x = last[v[i - 1]][cnt[v[i - 1]]] - 1;
      cnt[v[i]]++;
      update(1, 0, n - 1, i - 1, x, -1);
      ans += 2 * query(1, 0, n - 1, 0, n - 1);
    }
    ans -= n;
    ans /= (1LL * n * n);
    cout << fixed << setprecision(10) << ans << endl;
  }
  return 0;
}

```