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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskC {
		public class VandI implements Comparable<VandI> {
			int v, i;

			public VandI(int v, int i) {
				this.v = v;
				this.i = i;
			}

			@Override
			public int compareTo(VandI o) {
				int x = Integer.compare(v, o.v);
				if (x == 0) {
					return Integer.compare(i, o.i);
				}
				return x;
			}

		}

		public void solve(int testNumber, InputReader in, PrintWriter out) {
			long n = in.nextInt();
			VandI[] a = new VandI[(int) n];
			for (int i = 0; i < n; i++) {
				a[i] = new VandI(in.nextInt(), i);
			}
			Arrays.sort(a);
			double numberOfOptions = (n * n);
			numberOfOptions /= 2;
			double uniqueValues = n;
			uniqueValues /= numberOfOptions * 2;
			for (long i = 2; i <= n; i++) {
				uniqueValues += (i * (n - i + 1)) / numberOfOptions;
			}
			int i = 1;
			while (i < n) {
				if (a[i].v == a[i - 1].v) {
					long l = a[i - 1].i + 1, r = n - a[i].i;
					long numberOfDiffrentSegment = l * r;
					uniqueValues -= numberOfDiffrentSegment / numberOfOptions;
				}
				i++;
			}
			out.println(uniqueValues);
		}

	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextFloat() {
			return Double.parseDouble(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}
}