Berland 正在经历艰难时期——泥土价格下降,这对该国经济造成打击。大家都知道伯兰是世界最大的泥土出口国!
Berland 总统被迫仅保留现有 n 个地铁站中的 k 个。
地铁车站一个接一个地排列在一条直线上,火车在行驶过程中连续经过车站。您可以假设站点位于 Ox 轴上,第 i 个站点位于坐标 xi 的点。在这种情况下,站点 i 和 j 之间的距离通过简单的公式 |xi - xj| 计算。
目前,交通运输部正在选择哪些车站关闭、哪些车站离开。显然,京城的居民不会对这项创新抱有太大的热情,所以决定将最好的一面展现给人们。交通部要选择这样k个车站,尽量减少地铁平均通勤时间!
假设火车速度恒定(为固定值),则地铁中的平均通勤时间计算为车站之间的成对距离之和除以对数(即 $$\frac{n \cdot (n-1)}{2}$$),再除以火车速度。
帮助交通部长解决这个难题。编写一个程序,根据给定的车站位置,选择 k 个车站,使地铁的平均通勤时间最小化。
输入
输入的第一行包含整数 n (3 ≤ n ≤ 3·105) — 创新之前的站数。第二行包含站点 x1、x2、...、xn (- 108 ≤ xi ≤ 108) 的坐标。第三行包含整数 k (2 ≤ k ≤ n - 1) — 创新后的站数。
站点坐标是不同的,并且不一定已排序。
输出
打印 k 个不同整数 t1, t2, ..., tk (1 ≤ tj ≤ n) 的序列 — 以任意顺序创新后应留下的站号。假设站点按照输入中给出的顺序编号为 1 到 n。你打印的车站数量必须是所有可能选择k个车站的方式中平均通勤时间最小的。如果有多种这样的方式,您可以打印其中任何一种。
示例
输入 #1
3 1 100 101 2
输出 #1
2 3
注意
在示例测试用例中,最佳答案是摧毁第一个站(x = 1)。这样平均通勤时间将等于 1。