P4998 信号站

扶贫行动来到了Q村，扶贫队准备在Q村修筑信号站，让Q村不再“远离尘世”,让人们获得丰富的外界信息。

Q村非常非常Qiong，整个村只有一条路。在这条路上，有N户人家，因为条件有限，所以一个点上可能有多户人家。因为山区运输条件落后，所以扶贫队只能修筑k个信号站，并且他们希望各电站的不合理值之和最小。信号站的不合理值是指该信号站到每户人家的距离之和。 扶贫队善于修筑电站，但是他们不擅长选址~~（因为数学不好QwQ）~~，他们希望你>>编程高手，来帮助他们选择修筑信号站的最佳地点，使得k个信号站的不合理值最小。 距离求解方法:若某信号站的坐标为x,某户人家的坐标为y,那么该信号站与该人家的距离为|x-y|（即取绝对值）。 数据保证人家数大于信号站数。放置信号站的位置坐标必须为整数。一个位置上只能放一个信号站。

无

无

#### 样例解释 在2和3的位置上放置信号站（方案不唯一）。 #### 数据范围 对于 $ 70\% $ 的数据，$ n,k\leq 10^3 $； 对于 $ 100\% $ 的数据，$ n \leq 1000000, 0 \leq a_i \leq 10 ^ 6 $。