给定 n 个数字 p1、p2、...、pn 的排列。我们执行以下类型的 k 个操作:均匀随机选择两个索引 l 和 r (l ≤ r) 并反转元素 pl, pl + 1, ..., pr 的顺序。您的任务是找到结果排列中反转次数的预期值。
输入
输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 109)。下一行包含 n 个整数 p1, p2, ..., pn — 给定的排列。所有 pi 都不同,范围从 1 到 n。
该问题由三个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。
- 在子问题 G1(3 点)中,约束 1 ≤ n ≤ 6、1 ≤ k ≤ 4 将成立。
- 在子问题 G2(5 分)中,约束 1 ≤ n ≤ 30、1 ≤ k ≤ 200 将成立。
- 在子问题 G3(16 点)中,约束 1 ≤ n ≤ 100、1 ≤ k ≤ 109 将成立。
输出
输出绝对或相对误差不超过 1e - 9 的答案。
示例
输入 #1
3 1 1 2 3
输出 #1
0.833333333333333
输入 #2
3 4 1 3 2
输出 #2
1.458333333333334
注意
考虑第一个样本测试。我们将随机选择一个排列区间 (1, 2, 3)(没有反转)并反转其元素的顺序。在概率为 $$\frac{1}{2}$$ 的情况下,区间将由单个元素组成,并且排列不会改变。我们将以 $${ \frac { 1 } { 6 } }$$ 的概率反转前两个元素的顺序并获得具有一次反转的排列 (2, 1, 3)。以相同的概率,我们可以选择由最后两个元素组成的区间,这将导致具有一次反转的排列 (1, 3, 2)。最后,随机选取的区间将以 $${ \frac { 1 } { 6 } }$$ 的概率包含所有元素,从而导致具有 3 次反转的排列 (3, 2, 1)。因此,预期的反转次数等于 $${ \frac { 1 } { 2 } } \cdot 0 + { \frac { 1 } { 6 } } \cdot 1 + { \frac { 1 } { 6 } } \cdot 1 + { \frac { 1 } { 6 } } \cdot 3 = { \frac { 5 } { 6 } }$$。