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 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 + _p_1, a__l - 1 + _p_2, ..., a__l - 1 + p__k - 1, a__l - 1 + p__k, 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.

给你一个 $1$ 到 $n$ 的排列。你将对该排列恰好执行一次如下操作：随机选取一个连续子段，并对该子段内的元素进行随机重排（即均匀随机打乱）。形式化地描述如下：

1. 随机选取一个连续子段 $[l, r]$。所有满足 $1 \le l \le r \le n$ 的 $\frac{n(n+1)}{2}$ 个可能子段被选中的概率均等。
2. 记 $k = r - l + 1$，即所选子段的长度。再随机选取一个 $1$ 到 $k$ 的排列 $p_1, p_2, \dots, p_k$。所有 $k!$ 个排列被选中的概率均等。
3. 将该排列作用于所选子段上的元素：即原排列
   $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$
   被变换为
   $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$。

逆序对是指一对位置（不一定相邻）上元素的相对顺序错误。换言之，逆序对的数量等于满足 $i < j$ 且 $a_i > a_j$ 的数对 $(i, j)$ 的个数。
求在执行上述恰好一次操作后，所得排列中逆序对数量的期望值。

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 排列的长度。

第二行包含 $n$ 个互不相同的整数，取值范围为 $1$ 到 $n$ —— 排列的元素。

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 .

输出一个实数值——逆序对的期望数量。若你的答案的绝对或相对误差不超过 $10^{-9}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的答案为 $b$。当满足 时，评测程序将判定你的答案正确。