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 JAVA):

Solution:


import java.math.BigInteger;
import java.util.StringTokenizer;
import java.util.*;
import java.io.*;
public class Wtf {
    public static void main(String[] args) throws IOException {
        Ifmo ifmo = new Ifmo();
    }
}

class Ifmo {
    ArrayList<Integer> Graph[];
    int n, l, m, primes, timer;
    char[][] field;
    ArrayList<FUCKINGVERTEX> Ribs;
    int[][] roofs, ans, up;
    Vertex[][] highes;
    ArrayList<Integer> fin;
    static int cur;
    int[] p, size, tin, tout;
    boolean[] used;
    int logn;
    int[][] pref;
    int[][] longest;
    int[][][] dp = new int[31][31][51];
    long mod;
    ArrayList<Integer>[] tree, bit;
    Ifmo() throws IOException {
        FScanner fs = new FScanner(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int n = fs.nextInt();
        int[] mas = new int[n];
        for (int i =0 ; i<n;i++)
            mas[i] = fs.nextInt();
        ArrayList<Integer>[] ss = new ArrayList[(int) (1e6+1)];
        for (int i = 0; i<1e6+1; i++)
            ss[i] = new ArrayList<>();
        for (int i =0 ; i<n; i++)
            ss[mas[i]].add(i);
        long r = -n;
        for (int i = 0; i<1e6+1; i++) {
            if (ss[i].size() !=0) {
                for (int j = 0; j<ss[i].size(); j++) {
                    int a = ss[i].get(j)+1;
                    int b = j == 0? 0 : ss[i].get(j-1)+1;
                    r+=2L*(a-b)*(n-a+1);
                }
            }
        }
        double q =r;
        q=  q/n/n;
        pw.println(q);
        pw.close();
    }

    private void dfs1(int v, int p) {
        used[v] = true;
        if (v !=0) {
            longest[v][0] = gcd(longest[p][0], size[v]);
        }
        for (int i = 0; i<tree[v].size(); i++) {
            if (!used[tree[v].get(i)])
                dfs1(tree[v].get(i), v);
        }
    }

    void dfs_combo(int cur, int it,  int[] p, int[] q) {
        used[cur] = true;
        if (q[cur] == -1 || q[cur] == p[cur]);
    }

    void dfs(int cur, int[] mas, HashMap<Integer, Integer> numofv, HashMap<Integer, HashSet<Integer>> fullis, HashSet<Integer> currents, ArrayList<Integer>[] bin) {
        used[cur] = true;
        if (bin[mas[cur]].size() == 0)
            primes++;
        else {
            currents.add(mas[cur]);
            for (int i = 0; i<bin[cur].size(); i+=2) {
                int val = bin[cur].get(i);
                int how = bin[cur].get(i+1);
                if (numofv.containsKey(val)) {

                }
            }
        }


    }

    boolean upper(int a, int b) {
        return tin[a]<=tin[b] && tout[a]>=tout[b];
    }

    int lca(int a, int b) {
        if (upper(a, b)) return a;
        if (upper(b, a)) return b;
        for (int i = logn-1; i>=0; i--) {
            if (!upper(up[a][i], b))
                a = up[a][i];
        }
        return up[a][0];
    }



    int log_2(int g) {
        int s = 1;
        int ans = 0;
        while (g>=s)
        {
            ans++;
            s*=2;
        }
        return ans;
    }

    int dsu_get(int v) {
        return p[v] == v? v : (p[v] = dsu_get(p[v]));
    }

    void dsu_unit(int a, int b) { // a or dsu_get(a)? what's your choice?
        if (a!=b) {
            if (size[b]>size[a])
            {
                int q = a;
                a = b;
                b = q;
            }
            p[b] = a;
            size[a]+=size[b];
        }
    }
    int gcd (int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd (b, a % b);
    }
}

class forStr {
    int a, b, size;
    forStr(int a1, int b1, int size1) {
        a = a1;
        b = b1;
        size = size1;
    }
}
class Pair implements Comparable<Pair> {
    int x, y;
    Pair(int x1, int y1) {
        x = x1;
        y = y1;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(x, o.x);
    }
}

class Lines implements Comparable<Lines> {
    int pos;
    boolean start;
    Lines(int x, boolean f) {
        pos = x;
        start = f;
    }

    @Override
    public int compareTo(Lines o) {
       return Integer.compare(pos, o.pos);
    }
}

class Vertex implements Comparable<Vertex> {
    int  b, c;
    int a;
    Vertex(int a1, int b1, int c1) {
        a = a1;
        b = b1;
        c = c1;
    }

    @Override
    public int compareTo(Vertex o) {
        return Long.compare(c, o.c);
    }
}

class FUCKINGVERTEX implements Comparable<FUCKINGVERTEX> {
    int a, b, c, d;
    FUCKINGVERTEX(int a1, int b1, int c1, int d1) {
        a = a1;
        b = b1;
        c = c1;
        d = d1;
    }

    @Override
    public int compareTo(FUCKINGVERTEX o) {
        return Integer.compare(a, o.a);
    }
}
class FScanner {
    StringTokenizer st;
    BufferedReader reader;
    FScanner(InputStreamReader isr) throws IOException {
        reader = new BufferedReader(isr);
    }

    String nextLine() throws IOException {
        return reader.readLine();
    }

    String nextToken() throws IOException{
        while (st == null || !st.hasMoreTokens()) {
            String s = reader.readLine();
            if (s == null)
                return null;
            st = new StringTokenizer(s);
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    char nextChar() throws IOException {
        return (char) reader.read();
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
}