给你一个从 1 到 n 的整数排列。一旦您将以下操作应用于此排列:选择一个随机段并打乱其元素。正式:
1. 从 l 到 r 中随机选择一段(连续子序列)。所有 $$\frac{n(n+1)}{2}$$ 线段都是等概率的。
2.设k = r - l + 1,即所选线段的长度。选择从 1 到 k 的整数的随机排列,p1, p2, ..., pk。都k!排列是等概率的。
3. 该排列应用于所选段的元素,即排列a1, a2, ..., al - 1, al, al + 1, ..., ar - 1, ar, ar + 1, ..., an 转换为a1, a2, ..., al - 1, al - 1 + p1, al - 1 + p2, .. ., al - 1 + pk - 1, al - 1 + pk, ar + 1, ..., an。
如果一对元素(不一定相邻)具有错误的相对顺序,则反转。换句话说,反转次数等于 (i, j) 对的数量,使得 i < j 且 ai > aj。在我们应用上述一项操作后,求出预期的反转次数。
输入
第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 排列的长度。
第二行包含 n 个从 1 到 n 的不同整数 — 排列的元素。
输出
打印一个实数值——预期的反转次数。如果您的答案的绝对或相对误差不超过 10 - 9,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $${ \frac { | 则检查程序将认为您的答案正确。 a - b | } { \operatorname* { m a x } ( 1, b ) } } \leq 1 0 ^ { - 9 }$$。
示例
输入 #1
3 2 3 1
输出 #1
1.916666666666666666666666666667