eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1.5 секунда
Лимит использования памяти 512 MiB

Містер А знайшов у своїй шафі послідовність з n магічних кульок. Всі ці магічні кульки є кульками різного кольору, для зручності кольори пронумеровано цілими числами від 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.

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

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

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

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

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

Пример

Входные данные #1
6 6
1 5 3 2 6 4
Выходные данные #1
1 2 5 3 6 4 
Входные данные #2
6 5
2 3 1 5 6 4
Выходные данные #2
1 4 2 3 5 

Оценивание

  1. (8 балів): n\le 10^5, k=1;

  2. (5 балів): n\le 10^5, k=2;

  3. (19 балів): n\le 14;

  4. (16 балів): n\le 10^3;

  5. (10 балів): n\le 10^5, k\le 20;

  6. (24 бали): n\le 10^5;

  7. (18 балів): без додаткових обмежень.

Автор Ihor Barenblat