当前没有测试数据。

问题描述

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

输入格式

输入共 $2$ 行。

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

第二行为 $n$ 个由空格隔开的正整数 $a_1,a_2,...,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≤10^2$。

对于 $40\%$ 的数据，保证 $n≤10^3$。

对于 $100\%$ 的数据，保证 $n≤10^5$，$0<a_i≤10^9$，$0<k≤n$。