Truy vấn ngẫu nhiên

Cho một mảng $a$ gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$.

Ta chọn hai số nguyên $l$ và $r$ trong đoạn từ $1$ đến $n$ (chọn ngẫu nhiên, đồng khả năng và độc lập với nhau). Nếu $l>r$ thì đổi chỗ $l$ và $r$. Sau đó xét đoạn con của mảng từ chỉ số $l$ đến chỉ số $r$ (tính cả hai đầu, đánh chỉ số từ $1$).

Hãy tính kỳ vọng của số lượng phần tử phân biệt (số giá trị khác nhau) trong đoạn con đó.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số thực: kỳ vọng của số phần tử phân biệt trong đoạn được chọn.

Đáp án được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án chuẩn không vượt quá ${10}^{-4}$.

Ràng buộc

• $1\le n\le {10}^6$
• $1\le a_i\le {10}^6$

Ví dụ