Problems
Магічні кульки Містера А
Магічні кульки Містера А
Містер А знайшов у своїй шафі послідовність з $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}
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