Мистер А-nın Sehrli Topları#10363

Мистер А-nın Sehrli Topları

1,5 saniyə

512 meqabayt

Çox çətin

Mister A dolabında $n$ sehrli topdan ibarət bir sıra tapdı. Bu sehrli topların hər biri fərqli rənglərdədir və rahatlıq üçün rənglər $1$ -dən $n$ -ə qədər tam ədədlərlə nömrələnib. Qeyd edək ki, Mister A-nın toplarının sayı cütdür.

Bundan əlavə, Mister A topların rənglərini yazacağı $Q$ adlı bir tam ədədlər massivi hazırlayıb. Əvvəlcə $Q$ massivi boşdur.

Mister A aşağıdakı növ əməliyyatları $\frac{n}{2}$ \frac{n}{2} dəfə yerinə yetirməyi planlaşdırır: ardıcıllıqda qonşu olan iki topu seçəcək, onları ardıcıllıqdan çıxaracaq və çıxarılan topların rənglərini $Q$ massivinin əvvəlinə əlavə edəcək. Çıxarılan toplar $Q$ massivində ilkin ardıcıllıqda olduğu kimi nisbi qaydada olacaq. Ardıcıllıqdan elementlər çıxarıldıqdan sonra ardıcıllığın iki hissəsi birləşərək yeni bir ardıcıllıq əmələ gətirir.

Məsələn, topların rəng ardıcıllığı ${1, 5, 3, 2, 6, 4}$ \left\{1,5,3,2,6,4\right\} olarsa, əvvəlcə $Q$ massivinin əvvəlinə ${2, 6}$ \left\{2,6\right\} cütünü əlavə etmək, sonra ${3, 4}$ \left\{3,4\right\} cütünü əlavə etmək və sonda ${1, 5}$ \left\{1,5\right\} cütünü əlavə etmək olar — yaranan $Q$ massivi $[1, 5, 3, 4, 2, 6]$ [1,5,3,4,2,6] olacaq.

İndi Mister A-ya maraqlıdır ki, $\frac{n}{2}$ \frac{n}{2} əməliyyatı yerinə yetirərək leksikoqrafik olaraq minimal olan $Q$ massivini necə əldə etmək olar. Xatırladaq ki, leksikoqrafik qayda aşağıdakı kimi müəyyən edilir. İki massivimiz olsun. İki massivdə fərqli olan ilk mövqeyi tapaq. Əgər bu mövqedə birinci massivdəki element ikinci massivdəki elementdən kiçikdirsə, onda birinci massiv leksikoqrafik olaraq ikinci massivdən kiçikdir, əks halda — əksinə, birinci massiv böyükdür. Məsələn, aşağıdakı bərabərsizliklər doğrudur: $[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].

Mister A-ya minimal mümkün $Q$ massivinin ilk $k$ elementini tapmağa kömək edin.

Giriş

Birinci sətir iki tam ədəd $n$ və $k$ $(1 \leq k \leq n \leq 1 0^{6})$ (1\le k\le n\le 10^6) ehtiva edir. $n$ -in cüt olduğu təmin edilir.

İkinci sətir $n$ fərqli tam ədəd $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) ehtiva edir — topların rəng ardıcıllığı.

Çıxış

Minimal mümkün $Q$ massivinin ilk $k$ elementi olan $q_{1}, q_{2}, \dots, q_{k}$ q_1,q_2,\dots,q_k tam ədədlərini çıxarın.

Nümunələr

Nümunə 1

Nümunə 2

Bal hesablama

( $8$ bal): $n \leq 1 0^{5}, k = 1$ n\le 10^5, k=1;
( $5$ bal): $n \leq 1 0^{5}, k = 2$ n\le 10^5, k=2;
( $19$ bal): $n \leq 14$ n\le 14;
( $16$ bal): $n \leq 1 0^{3}$ n\le 10^3;
( $10$ bal): $n \leq 1 0^{5}, k \leq 20$ n\le 10^5, k\le 20;
( $24$ bal): $n \leq 1 0^{5}$ n\le 10^5;
( $18$ bal): əlavə məhdudiyyətlərsiz.