题目描述

熊大和熊二在玩游戏。他们将 $n$ 个正整数 $a_1, a_2, \dots, a_n$ 排成一行，然后各用一个长度为 $k$ 的框在这个数组中各自随机框选出一段长度为 $k$ 的连续子序列（随机框选指在合法的 $n - k + 1$ 个连续子序列中均匀随机）。熊大记录了他框出的 $k$ 个数中的最大值 $P$，熊二记录了他框出的 $k$ 个数的最小值 $Q$，他们突然有个疑问：$P - Q$ 的期望是多少？

输入格式

输入共 $2$ 行。

第一行为两个正整数 $n, k$。

第二行为 $n$ 个由空格隔开的正整数 $a_1, a_2, \dots, a_n$。

输出格式

输出共 $1$ 行，一个浮点数（请保留两位小数）。

3 2
1 2 3

1.00

提示

样例说明

一共有四种情况：

• 熊大框出 $[1, 2]$，$P = 2$；熊二框出 $[1, 2]$，$Q = 1$，$P - Q = 1$。
• 熊大框出 $[1, 2]$，$P = 2$；熊二框出 $[2, 3]$，$Q = 2$，$P - Q = 0$。
• 熊大框出 $[2, 3]$，$P = 3$；熊二框出 $[1, 2]$，$Q = 1$，$P - Q = 2$。
• 熊大框出 $[2, 3]$，$P = 3$；熊二框出 $[2, 3]$，$Q = 2$，$P - Q = 1$。

所以 $P - Q$ 的期望为 $(1 + 0 + 2 + 1) / 4 = 1.00$。

评测用例规模与约定

• 对于 $20\%$ 的数据，保证 $n \leq 10^2$。
• 对于 $40\%$ 的数据，保证 $n \leq 10^3$。
• 对于 $100\%$ 的数据，保证 $n \leq 10^5$，$0 < a_i \leq 10^9$，$0 < k \leq n$。