Магические шарики Мистера А

Мистер А обнаружил в своём шкафу последовательность из $n$ магических шариков. Все шарики имеют разные цвета, и для удобства цвета пронумерованы целыми числами от $1$ до $n$. Количество шариков у Мистера А всегда чётное.

У Мистера А также есть массив целых чисел $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. ($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$ баллов): без дополнительных ограничений.