e-olymp
Competitions

Ukrainian Olympiad in Informatics, III Stage, I Round

Магічні кульки Містера А

Містер А знайшов у своїй шафі послідовність з $n$ магічних кульок. Всі ці магічні кульки є кульками \textbf{різного} кольору, для зручності кольори пронумеровано цілими числами від $1$ до $n$. Звісно у Містера А кількість кульок парна. Також, у Містера А є масив цілих чисел $Q$, куди він записуватиме кольори кульок. Початково масив $Q$ порожній. Містер А планує виконати $\frac{n}{2}$ операцій наступного виду: герой вибиратиме пару кульок, які є сусідніми у послідовності, видалятиме їх з послідовності та додаватиме кольори видалених кульок у початок масиву $Q$. Кульки, що видаляються, матимуть такий самий відносний порядок у масиві $Q$ як і у початковій послідовності. Після видалення елементів з послідовності дві частини послідовності з'єднуються, утворюючи при цьому одну нову послідовність. Наприклад, якщо послідовність кольорів кульок рівна $\left\{1,5,3,2,6,4\right\}$, можна спочатку додати до початку масиву $Q$ пару елементів $\left\{2,6\right\}$, після чого додати пару елементів $\left\{3,4\right\}$, і наприкінці додати пару елементів $\left\{1,5\right\}$~--- утворений масив $Q$ буде рівним $[1,5,3,4,2,6]$. Тепер Містеру А цікаво, який лексикографічно мінімальний масив $Q$ можна отримати виконавши $\frac{n}{2}$ операцій. Нагадаємо, що лексикографічний порядок задається наступним чином. Нехай маємо два масиви. Знайдемо першу позицію, у якій елементи двох масивів відрізняються. Тоді якщо на цій позиції елемент першого масиву менший за елемент другого, то перший масив лексикографічно менший за другий, інакше "--- навпаки, перший масив більший за другий. Наприклад, виконуються наступні нерівності: $[10, 3, 1]$ < $[10, 4, 5]$, $[1, 1, 1] < [1, 2, 3], [1, 2, 3] < [10, 10, 10]$. Допоможіть Містеру А знайти $k$ перших елементів мінімально можливого масиву $Q$. \InputFile Перший рядок містить два цілі числа $n$ та $k$ $(1\le k\le n\le 10^6)$. Гарантується, що $n$~--- парне. Другий рядок містить $n$ \textbf{різних} цілих чисел $a_1,a_2,\dots,a_n$ $(1\le a_i\le n)$~--- кольори кульок послідовності. \OutputFile Виведіть $k$ цілих чисел $q_1,q_2,\dots,q_k$~--- перші елементи мінімально можливого масиву $Q$. \Scoring \begin{enumerate} \item ($8$ балів): $n\le 10^5, k=1$; \item ($5$ балів): $n\le 10^5, k=2$; \item ($19$ балів): $n\le 14$; \item ($16$ балів): $n\le 10^3$; \item ($10$ балів): $n\le 10^5, k\le 20$; \item ($24$ бали): $n\le 10^5$; \item ($18$ балів): без додаткових обмежень. \end{enumerate}
Time limit 1.5 second
Memory limit 512 MiB
Input example #1
6 6
1 5 3 2 6 4
Output example #1
1 2 5 3 6 4 
Input example #2
6 5
2 3 1 5 6 4
Output example #2
1 4 2 3 5 
Author Ihor Barenblat