406878: GYM102591 F Разделение на пары

Есть $$$n$$$ студентов. У каждого студента есть уровень силы в олимпиадах. Причем у всех студентов уровни силы различные. Сила $$$i$$$-го студента равна $$$s_i$$$. Проводится парная олимпиада. Студентов нужно разбить на пары. Если $$$i$$$-й студент и $$$j$$$-й студент будут в одной паре, то сила их пары будет $$$min(s_i, s_j)$$$. Вы хотите разбить студентов так, чтобы сумма сил пар была максимальной. Каждый студент может быть максимум в одной паре. К несчастью, $$$n$$$ - нечетно. В любом случае один из студентов останется без пары. Для каждого студента вы хотите найти максимальную сумму разбиения на пары, в случае если этот студент останется без пары.

В первой строке задано одно целое число $$$n$$$ $$$(3 \le n \le 3 * 10^5$$$, $$$n$$$ - нечетно) – количество студентов. Во второй строке задан массив $$$s$$$ – сила студентов. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ выполняется $$$(1 \le s_i \le 10^9)$$$. Гарантируется, что все числа в массиве $$$s$$$ различные.

Выведите $$$n$$$ целых чисел. $$$i$$$-ое из них – ответ на задачу, если $$$i$$$-й студент останется без команды.

3
3 1 2

1 2 1