题目描述

在数轴上有 $N$ 只史莱姆，第 $i$ 只史莱姆位于坐标 $A_i$。这些坐标互不相同。每只史莱姆的质量为 $1$。另外，给定一个整数 $K$。

你需要首先选择 $K$ 只史莱姆，并将未被选中的史莱姆从数轴上移除。之后，被选中的史莱姆从时刻 $0$ 开始按照以下规则移动：

• 每只史莱姆的移动方式如下：设自己右侧（坐标更大）所有史莱姆的质量总和为 $R$，左侧（坐标更小）所有史莱姆的质量总和为 $L$。则该史莱姆以速度 $R-L$ 移动。注意速度可以为负，即当 $R-L<0$ 时，史莱姆向数轴负方向移动。

当有两只及以上的史莱姆同时到达同一坐标时，它们会合体。合体后的史莱姆质量为合体前所有史莱姆质量之和。合体后的史莱姆也按照上述规则继续移动。

$K$ 只史莱姆会不断合体，最终只剩下一只史莱姆。该史莱姆诞生的瞬间记为时刻 $t$。你的目标是，合理选择 $K$ 只史莱姆，使得 $t$ 最大。请输出 $t$ 的最大值。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出一个实数作为答案。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

输入输出样例 #1

输入 #1

3 2
0 1 2

输出 #1

1.00000000000000000000

输入输出样例 #2

输入 #2

4 3
0 1 4 9

输出 #2

2.83333333333333333333

输入输出样例 #3

输入 #3

4 4
0 1 2 3

输出 #3

0.50000000000000000000

输入输出样例 #4

输入 #4

20 6
0 3441380 120768398 229897071 231209282 232046760 254924545 325399248 385631087 400098966 480503302 501372095 502644652 524585010 541761042 691400171 725009462 767549897 837806226 927396743

输出 #4

135453315.33333333333333333333

说明/提示

限制条件

• $2 \leq K \leq N \leq 250000$
• $0 = A_1 < A_2 < \cdots < A_N \leq 10^9$
• 所有输入值均为整数

样例解释 1

• 选择第 $1$ 和第 $2$ 只史莱姆时，$t=0.5$。
• 选择第 $1$ 和第 $3$ 只史莱姆时，$t=1$。
• 选择第 $2$ 和第 $3$ 只史莱姆时，$t=0.5$。 因此答案为 $1$。

样例解释 2

当选择第 $1,2,4$ 只史莱姆时，史莱姆的移动过程如下：

• 将第 $1,2,4$ 只史莱姆分别记为 $X,Y,Z$。
• 时刻 $0$：$X,Y,Z$ 分别以速度 $+2,0,-2$ 开始移动。
• 时刻 $1/2$：$X$ 和 $Y$ 在坐标 $1$ 处合体，合体后的史莱姆记为 $XY$，$XY$ 以速度 $1$ 继续移动，$Z$ 此时在坐标 $8$，速度仍为 $-2$。
• 时刻 $17/6$：$XY$ 和 $Z$ 在坐标 $10/3$ 处合体。 因此 $t=17/6$。无法使 $t$ 更大，所以答案为 $17/6$。