ou 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 Format
The first line contains one integer number The first line contains one integer number n . The second line contains n integer numbers a1, a2, … an — elements of the array. (1 ≤ ai ≤ 106)
Constraints
1 ≤ n ≤ 10^6
Output Format
Print one number — the expected number of unique elements in chosen segment.
NOTE: Print your answer upto the precision of 6 decimal places.
Sample Input
2
1 2
Sample Output
1.500000
Please give me some hint in this probelm