Subway Innovation

题意翻译

### 题目描述： 直线上 $n$ 个点，定义点 $i, j$之间的距离为 $|x_i-x_j|$。保留 $k$ 个点，使这些点**两两之间的距离和**最小。输出 $k$ 个点的下标。 ### 输入格式： 第一行，一个正整数 $n$，表示点的个数。 第二行，$n$ 个整数 $x_1,x_2,...,x_n$，表示每个点的位置。 第三行，一个正整数 $k$，含义如题目描述。 ### 输出格式： 一行，$k$ 个正整数 $t_1,t_2,...,t_k$，表示保留的点的下标。两个正整数之间用一个空格连接。 注意答案不唯一，所有正确的答案都会被接受。

题目描述

Berland is going through tough times — the dirt price has dropped and that is a blow to the country's economy. Everybody knows that Berland is the top world dirt exporter! The President of Berland was forced to leave only $ k $ of the currently existing $ n $ subway stations. The subway stations are located on a straight line one after another, the trains consecutively visit the stations as they move. You can assume that the stations are on the $ Ox $ axis, the $ i $ -th station is at point with coordinate $ x_{i} $ . In such case the distance between stations $ i $ and $ j $ is calculated by a simple formula $ |x_{i}-x_{j}| $ . Currently, the Ministry of Transport is choosing which stations to close and which ones to leave. Obviously, the residents of the capital won't be too enthusiastic about the innovation, so it was decided to show the best side to the people. The Ministry of Transport wants to choose such $ k $ stations that minimize the average commute time in the subway! Assuming that the train speed is constant (it is a fixed value), the average commute time in the subway is calculated as the sum of pairwise distances between stations, divided by the number of pairs (that is ) and divided by the speed of the train. Help the Minister of Transport to solve this difficult problem. Write a program that, given the location of the stations selects such $ k $ stations that the average commute time in the subway is minimized.

输入输出格式

输入格式

The first line of the input contains integer $ n $ ( $ 3<=n<=3·10^{5} $ ) — the number of the stations before the innovation. The second line contains the coordinates of the stations $ x_{1},x_{2},...,x_{n} $ ( $ -10^{8}<=x_{i}<=10^{8} $ ). The third line contains integer $ k $ ( $ 2<=k<=n-1 $ ) — the number of stations after the innovation. The station coordinates are distinct and not necessarily sorted.

输出格式

Print a sequence of $ k $ distinct integers $ t_{1},t_{2},...,t_{k} $ ( $ 1<=t_{j}<=n $ ) — the numbers of the stations that should be left after the innovation in arbitrary order. Assume that the stations are numbered 1 through $ n $ in the order they are given in the input. The number of stations you print must have the minimum possible average commute time among all possible ways to choose $ k $ stations. If there are multiple such ways, you are allowed to print any of them.

输入输出样例

输入样例 #1

3
1 100 101
2

输出样例 #1

2 3 

说明

In the sample testcase the optimal answer is to destroy the first station (with $ x=1 $ ). The average commute time will be equal to 1 in this way.