Задача №1382. Трубочист
После пожара 1812 года на одной из главных улиц Москвы уцелел лишь один дом. Вернувшиеся после победы жители решили вновь поселиться на этой улице. При этом каждый решил построить себе дом такой же высоты, каким он был у него до пожара.
Дома будут строиться вплотную друг другу, а крыши соседних домов будут соединяться лестницами (длина лестницы равна разнице высот домов), чтобы трубочист мог путешествовать по крышам и чистить трубы.
Когда план постройки домов был уже почти утвержден, свое веское слово сказал Главный Трубочист. Он попросил построить дома так, чтобы суммарная длина лестниц была минимальной. Помогите ему составить такой план постройки домов.
Во входном файле записано сначала число N (1 ≤ N ≤ 10000), затем N чисел — высоты домов до пожара (это натуральные числа от 1 до 109), и затем K — номер уцелевшего дома.
В выходной файл выведите высоты домов в таком порядке, чтобы выполнялось требование Главного Трубочиста. Обратите внимание, что K-ый дом (уцелевший) перестраивать не нужно (и следовательно его высота должна остаться прежней).
5 1 3 4 2 6 2
6 3 4 2 1