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

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

1,5 секунди

512 мегабайтів

Дуже складна

Містер А знайшов у своїй шафі послідовність з $n$ магічних кульок. Всі ці магічні кульки є кульками різного кольору, для зручності кольори пронумеровано цілими числами від $1$ до $n$ . Звісно у Містера А кількість кульок парна.

Також, у Містера А є масив цілих чисел $Q$ , куди він записуватиме кольори кульок. Початково масив $Q$ порожній.

Містер А планує виконати $\frac{n}{2}$ \frac{n}{2} операцій наступного виду: герой вибиратиме пару кульок, які є сусідніми у послідовності, видалятиме їх з послідовності та додаватиме кольори видалених кульок у початок масиву $Q$ . Кульки, що видаляються, матимуть такий самий відносний порядок у масиві $Q$ як і у початковій послідовності. Після видалення елементів з послідовності дві частини послідовності з'єднуються, утворюючи при цьому одну нову послідовність.

Наприклад, якщо послідовність кольорів кульок рівна ${1, 5, 3, 2, 6, 4}$ \left\{1,5,3,2,6,4\right\}, можна спочатку додати до початку масиву $Q$ пару елементів ${2, 6}$ \left\{2,6\right\}, після чого додати пару елементів ${3, 4}$ \left\{3,4\right\}, і наприкінці додати пару елементів ${1, 5}$ \left\{1,5\right\} — утворений масив $Q$ буде рівним $[1, 5, 3, 4, 2, 6]$ [1,5,3,4,2,6].

Тепер Містеру А цікаво, який лексикографічно мінімальний масив $Q$ можна отримати виконавши $\frac{n}{2}$ \frac{n}{2} операцій. Нагадаємо, що лексикографічний порядок задається наступним чином. Нехай маємо два масиви. Знайдемо першу позицію, у якій елементи двох масивів відрізняються. Тоді якщо на цій позиції елемент першого масиву менший за елемент другого, то перший масив лексикографічно менший за другий, інакше — навпаки, перший масив більший за другий. Наприклад, виконуються наступні нерівності: $[10, 3, 1]$ [10, 3, 1] < $[10, 4, 5]$ [10, 4, 5], $[1, 1, 1] < [1, 2, 3], [1, 2, 3] < [10, 10, 10]$ [1, 1, 1] < [1, 2, 3], [1, 2, 3] < [10, 10, 10].

Допоможіть Містеру А знайти $k$ перших елементів мінімально можливого масиву $Q$ .

Вхідні дані

Перший рядок містить два цілі числа $n$ та $k$ $(1 \leq k \leq n \leq 1 0^{6})$ (1\le k\le n\le 10^6). Гарантується, що $n$ — парне.

Другий рядок містить $n$ різних цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1,a_2,\dots,a_n $(1 \leq a_{i} \leq n)$ (1\le a_i\le n) — кольори кульок послідовності.

Вихідні дані

Виведіть $k$ цілих чисел $q_{1}, q_{2}, \dots, q_{k}$ q_1,q_2,\dots,q_k — перші елементи мінімально можливого масиву $Q$ .

Приклади

Приклад 1

Приклад 2

Оцінювання

( $8$ балів): $n \leq 1 0^{5}, k = 1$ n\le 10^5, k=1;
( $5$ балів): $n \leq 1 0^{5}, k = 2$ n\le 10^5, k=2;
( $19$ балів): $n \leq 14$ n\le 14;
( $16$ балів): $n \leq 1 0^{3}$ n\le 10^3;
( $10$ балів): $n \leq 1 0^{5}, k \leq 20$ n\le 10^5, k\le 20;
( $24$ бали): $n \leq 1 0^{5}$ n\le 10^5;
( $18$ балів): без додаткових обмежень.