Областная олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Задача C. Разделяем на пары

Есть массив $a$ из $n$ целых чисел. Для каждого $k$ от $1$ до $\lfloor$ $\frac{n}{2}$ $\rfloor$, найдите $k$ различных пар, что сумма абсолютных разностей пар была минимизирована. Более формально, выберите $2k$ различных индексов, и разбейте их на $k$ пар ($i_1$, $j_1$), ($i_2$, $j_2$), $\dots$, ($i_k$, $j_k$), чтобы значение $|a_{i_1} - a_{j_1}|$ + $|a_{i_2} - a_{j_2}|$ + $\dots$ + $|a_{i_k} - a_{j_k}|$ было минимально.

Формат входного файла

В первой строке находятся одно целое число $n$ ($1$ $\le$ $n$ $\le$ $2*10^5$).

Во второй строке находятся $n$ целых чисел $a_1$, $a_2$,…, $a_n$ ($1$ $\le$ $a_i$ $\le$ $10^9$).

Формат выходного файла

Выведите $\lfloor$ $\frac{n}{2}$ $\rfloor$ целых чисел, где k-е число является ответом $k$ пар.

Примеры

Входные данные

11
31 12 1 36 41 57 21 79 86 63 97

Выходные данные

5 11 18 27 39