3-й этап Республиканской олимпиады по информатике 2021-2022, 1 тур

Есеп С. Жұптарға бөлеміз

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

$n$ бүтін сандардан тұратын $a$ массиві бар. 1-ден $\lfloor \frac{n}{2} \rfloor$-дейінгі әр $k$ үшін, жұптардың абсолютті айырмашылықтарының қосындысы минимал болатын $k$ әр түрлі жұптарды табыңыз. Басқаша айтқанда, $|a_{i_1} - a_{j_1}| + |a_{i_2} - a_{j_2}| + \dots + |a_{i_k} - a_{j_k}|$ мәні минимал болатын, $(i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)$ жұптарын табыңыз. Массивтің әр элементі ең көбі бір жұпта болуы керек.

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

Бірінші жолда $n$ бүтін саны бар ($1 <= n <= 2 * 10^5$) - массив ұзындығы. Екінші жолда $n$ бүтін сандар берілген $a_1, a_2,..., a_n (1 <= a_i <= 10^9)$ - массив элементтері.

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

$\lfloor \frac{n}{2} \rfloor$ бүтін сандарды шығарыңыз, мұнда $k$-саны $k$ жұпқа арналған жауап болып табылады.

Система оценки

Бұл тапсырмада $6$ бөлікке бөлінеді:

1. $n <= 11$. $7$ баллға бағаланады.
2. $n <= 18$. $11$ баллға бағаланады.
3. $n <= 500$. $13$ баллға бағаланады.
4. $n <= 5000$. $15$ баллға бағаланады.
5. $a_i <= 5000$. $13$ баллға бағаланады.
6. мәселенің бастапқы шарттары. $41$ баллға бағаланады.

Примеры:

Вход

6
1 3 5 8 13 21

Ответ

2 5 13

Вход

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

Ответ

5 11 18 27 39

( Narkhan Kamzabek )