P4650 [COCI 2017/2018 #5] Karte

There are $N$ cards stacked together. On the $i$-th card, there is a number $a_i$, meaning that **at least** $a_i$ cards below it have incorrect information. If there are indeed at least $a_i$ cards below it with incorrect information, then the information on this card is correct; otherwise, the information on this card is incorrect. (We consider that below the bottom card there are $0$ incorrect cards.) Now you need to rearrange the order of the cards so that exactly $K$ cards have incorrect information.

The first line contains two positive integers $N$ and $K$ $(1 \le N \le 5 \times 10^5, 0 \le K \le N)$, representing the number of cards and the required number of incorrect pieces of information. The next $N$ lines each contain one number, representing the corresponding $a_i$ $(0 \le a_i \le 5 \times 10^5)$.

If no rearrangement exists, output $-1$. Otherwise, output the $a_i$ of the $N$ cards from top to bottom. If there are multiple solutions, output any one.

For $30\%$ of the testdata, $N \le 16$. For another $40\%$ of the testdata, $N \le 2000$. **Explanation of Sample 2:** The $5$-th card shows $2$, but there are only $0$ incorrect cards below it, so it is incorrect. The $4$-th card shows $1$. There is $1$ incorrect card below it (the $5$-th), so it is correct. The $3$-th card shows $0$. There is $1$ incorrect card below it (the $5$-th), so it is correct. The $2$-th card shows $3$, but there is only $1$ incorrect card below it (the $5$-th), so it is incorrect. The $1$-st card shows $3$, but there are only $2$ incorrect cards below it (the $5$-th and the $2$-nd), so it is incorrect. Therefore, there are $3$ incorrect cards in total. Translated by ChatGPT 5