CF749E Inversions After Shuffle

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 $\frac{n(n+1)}{2}$ 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},\dots,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},\dots,a_{l-1},a_{l},a_{l+1},\dots,a_{r-1},a_{r},a_{r+1},\dots,a_{n} $ is transformed to $ a_{1},a_{2},\dots,a_{l-1},a_{l-1+p_1},a_{l-1+p_2},\dots,a_{l-1+p_{k-1}},a_{l-1+p_k},a_{r+1},\dots,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\lt j $ and $ a_{i}\gt 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\le n\le 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 $\frac{\lvert a-b\rvert}{\max(1,b)}\leq10^{-9}$.