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 ≤ 10^6). The second line contains n integer numbers a_1, a_2, ... a_{n} (1 ≤ a_{i} ≤ 10^6) — 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 $\operatorname{min}(|x - y|, \frac{|x - y|}{x}) \leq 10^{-4}$, 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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Amortized analysis

Mathematics

Probability


Solutions:
n = int(input())
arr = [0]
arr = arr + list(map(int, input().split(' ')))

def getCounts(arr):
	last = {}
	ans = 0.0
	prev = 0.0
	res = 0.0
	for i in range(1, len(arr)):
		if arr[i] not in last:
			ans = prev + i
		else:
			ans = prev + i - last[arr[i]]
		prev = ans
		res += ans
		last[arr[i]] = i
	return res
ans = (2 * getCounts(arr) - n) / (n * n)
print('%.6f' % ans)


n = int(input())
a = list(map(int, input().split()))
d = {}

def push(d, x, i):
	if x not in d:
		d[x] = []
	d[x].append(i)
for (i, x) in enumerate(a):
	push(d, x, i)
S = 0
for arr in d.values():
	pre = -1
	for i in arr:
		S += 2 * (i - pre) * (n - i)
		pre = i
print((S - n) / (n * n))


n = int(input())
a = list(map(int, input().split()))
lastocc = [0] * 1000006
ans = [0] * n
ans[0] = 1
lastocc[a[0]] = 1
for i in range(1, n):
	ans[i] = ans[i - 1] + (i + 1 - lastocc[a[i]])
	lastocc[a[i]] = i + 1
print((2 * sum(ans) - n) / (n * n))


lim = 10 ** 7
last_occ = [0 for i in range(lim)]
n = int(input())
ans = [0 for i in range(n + 1)]
arr = [int(i) for i in input().split()]
arr.insert(0, 0)
for i in range(1, n + 1):
	ans[i] = ans[i - 1] + (i - last_occ[arr[i]])
	last_occ[arr[i]] = i
total_sum = sum(ans)
ans = round((2 * (total_sum - n) + n) / n ** 2, 6)
print(format(ans, '.6f'))


import sys
from collections import defaultdict
n = int(sys.stdin.buffer.readline().decode('utf-8'))
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
next_dic = defaultdict(list)
for i in range(n - 1, -1, -1):
	next_dic[a[i]].append(i)
fx = sum(((n - v[-1]) * 2 for v in next_dic.values()))
ans = 0
for i in range(n):
	j = next_dic[a[i]].pop()
	ans += fx - 1
	fx += -(n - j) * 2 + (n - next_dic[a[i]][-1] if next_dic[a[i]] else 0) * 2
print(ans / (n * n))