E. Метроны шинэ санаачлага

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берланд газар шорооны үнэ унаж эдийн засагт хүнд цохилт болж буй хэцүү цаг үеийг туулж байна. Хүн бүр Берланд бол шорооны шилдэг экспортлогч орон гэдгийг мэднэ.

Берландын ерөнхийлөгч одоо байгаа $n$ метроны буудлыг $k$ болгож багасгахаар болсон.

Метроны буудлууд шулуун дээр дарааллан байрласан ба метро дэс дарааллан буудлууд дээр очдог. Та эдгээр буудлууд $Ox$ тэнхлэгийн дагуу $i$-р буудал нь $x_i$ кординаттай байна гэж үз. $i$-р болон $j$-р буудлын хоорондох зайг $|x_i-x_j|$ томьёогоор олно.

Одоогоор тээврийн яам аль буудлыг нь хааж алийг нь үлдээх вэ гэж сонгож байна. Мэдээж хотын оршин суугчид энэхүү шинэчлэлтэнд тийм ч таатай хандахгүй байгаа. Тиймээс хүмүүст ашигтай талыг харуулахаар шийдсэн. Тээврийн яам метронд зарцуулах дундаж хугацаа хамгийн бага байхаар $k$ буудал сонгохыг хүсэж байна. Метроны хурд тогтмол. Метронд зарцуулах дундаж хугацааг хос буудал бүрийн хоорондох зайн нийлбэрийг нийт хос буудлыг тоо болон метроны хурданд хувааж олно.

Тээврийн яаманд энэхүү хэцүү асуудлыг шийдэхэд нь туслана уу.

Оролт

Эхний мөрөнд шинэчлэлтээс өмнөх буудлын тоо $n\ (3 ≤ n ≤ 3·10^5)$, дараагийн мөрөнд буудлын координатууд болох $x_1$, $x_2$,..., $x_n$ $(-10^8≤x_i≤10^8)$, сүүлийн мөрөнд шинэчлэлтийн дараа үлдэх буудлын тоо $k$ өгөгдөнө.

Гаралт

Нэг мөрөнд $k$ ширхэг хоорондоо ялгаатай буудлын дугаарууд болох $t_1$, $t_2$,..., $t_k$-г дурын дарааллаар хэвлэ. Хэрвээ олон хариу байвал аль нэгийг нь хэвлэхэд болно.

Орчуулсан: Говьхүү

Жишээ тэстүүд

Оролт
3
1 100 101
2
Гаралт
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.

Сэтгэгдлүүдийг ачааллаж байна...