Inversions After Shuffle

给出一个 $1\sim n$ 的排列，从中等概率的选取一个连续段，设其长度为 $l$。对连续段重新进行等概率的全排列，求排列后整个原序列的逆序对的期望个数。

You are given a permutation of integers from $ 1 $ to $ n $ . Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally: 1. Pick a random segment (continuous subsequence) from $ l $ to $ r $ . All  segments are equiprobable. 2. Let $ k=r-l+1 $ , i.e. the length of the chosen segment. Pick a random permutation of integers from $ 1 $ to $ k $ , $ p_{1},p_{2},...,p_{k} $ . All $ k! $ permutation are equiprobable. 3. This permutation is applied to elements of the chosen segment, i.e. permutation $ a_{1},a_{2},...,a_{l-1},a_{l},a_{l+1},...,a_{r-1},a_{r},a_{r+1},...,a_{n} $ is transformed to $ a_{1},a_{2},...,a_{l-1},a_{l-1+p1},a_{l-1+p2},...,a_{l-1+pk-1},a_{l-1+pk},a_{r+1},...,a_{n} $ . Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs $ (i,j) $ such that $ i<j $ and $ a_{i}>a_{j} $ . Find the expected number of inversions after we apply exactly one operation mentioned above.

The first line contains a single integer $ n $ ( $ 1<=n<=100000 $ ) — the length of the permutation. The second line contains $ n $ distinct integers from $ 1 $ to $ n $ — elements of the permutation.

Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed $ 10^{-9} $ . Namely: let's assume that your answer is $ a $ , and the answer of the jury is $ b $ . The checker program will consider your answer correct, if .

3
2 3 1

1.916666666666666666666666666667