CF846F Random Query

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).

The first line contains one integer number $ n $ $ (1

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 , where $ x $ is jury's answer, and $ y $ is your answer.