Nghịch thế sau khi xáo trộn

Cho một hoán vị $a_1,a_2,\dots ,a_n$ của các số nguyên từ $1$ đến $n$. Ta thực hiện đúng một lần thao tác sau:

1. Chọn ngẫu nhiên một đoạn $[l,r]$ với $1\le l\le r\le n$. Tất cả ${\displaystyle \frac{n(n+1)}{2}}$ đoạn có xác suất được chọn bằng nhau.
2. Đặt $k=r-l+1$. Chọn ngẫu nhiên một hoán vị $p_1,p_2,\dots ,p_k$ của các số $1,2,\dots ,k$. Tất cả $k!$ hoán vị có xác suất bằng nhau.
3. Sắp xếp lại các phần tử của đoạn $[l,r]$ theo hoán vị $p$ vừa chọn: gọi $b_1,b_2,\dots ,b_k$ là các giá trị $a_l,a_{l+1},\dots ,a_r$ sau khi sắp xếp tăng dần; phần tử tại vị trí $l+t-1$ trong dãy mới bằng $b_{p_t}$. Nói cách khác, tập giá trị trong đoạn $[l,r]$ được giữ nguyên nhưng thứ tự được hoán vị một cách đều ngẫu nhiên.

Một nghịch thế là một cặp chỉ số $(i,j)$ với $i<j$ và $a_i>a_j$.

Hãy tính kỳ vọng của số nghịch thế trong dãy sau khi thực hiện đúng một thao tác như trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài của hoán vị.
• Dòng thứ hai chứa $n$ số nguyên phân biệt — các phần tử của hoán vị.

Dữ liệu ra

In ra một số thực — kỳ vọng số nghịch thế. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-9}$.

Ràng buộc

• $1\le n\le {10}^5$
• $a$ là một hoán vị của $1,2,\dots ,n$.

Ví dụ