P5156 [USACO18DEC] Sort It Out P

FJ has $N$ cows ($1 \leq N \leq 10^5$), labeled $1 \ldots N$, standing in a line. FJ likes his cows to be in increasing order, but unfortunately their order is currently scrambled. In the past, FJ used some groundbreaking algorithms such as "bubble sort" to sort his cows, but today he wants to be lazy. Instead, each time he will shout at one cow, "Get in order." When a cow is shouted at, she will make sure her position in the line is correct (from her point of view). If the cow immediately to her right has a smaller label than hers, they swap positions. Then, if the cow immediately to her left has a larger label than hers, they swap positions. In this way, the cow finishes "getting in order": from her point of view, cows to her left have smaller labels than hers, and cows to her right have larger labels than hers. FJ wants to choose a subset of the cows, then repeatedly go through this subset and shout at each selected cow in increasing order of label, repeating until all $N$ cows are sorted. For example, if he chooses the subset of cows with labels $\{2,4,5\}$, then he will shout at cow $2$, then cow $4$, then cow $5$. If the $N$ cows are still not sorted at that point, he will shout at these cows again, and continue repeating if necessary. Since FJ is not sure which cows are attentive, he wants this subset to be as small as possible. Also, he believes $K$ is a lucky number. Please help him find, among all minimum-size subsets that can sort all cows by repeated shouting, the $K$-th smallest subset in lexicographic order. We say that a subset $S$ of $\{1, \ldots, N\}$ is smaller than a subset $T$ in lexicographic order if the sequence of elements of $S$ (sorted in increasing order) is lexicographically smaller than the sequence of elements of $T$ (sorted in increasing order). For example, $\{1,3,6\}$ is lexicographically smaller than $\{1,4,5\}$.

The first line contains an integer $N$. The second line contains an integer $K$ ($1 \leq K \leq 10^{18}$). The third line contains $N$ space-separated integers, giving the cow labels from left to right. It is guaranteed that there are at least $K$ valid subsets.

Print the size of a minimum subset on the first line. Then output the cow labels in the $K$-th lexicographically smallest minimum subset, one per line, in increasing order.

At the beginning, the sequence is $ \mathtt{\:4\:\; 2\:\; 1\:\; 3\:} $. After FJ shouts at cow $1$, the sequence becomes $ \mathtt{\:1\:\; 4\:\; 2\:\; 3\:} $. After FJ shouts at cow $4$, the sequence becomes $ \mathtt{\:1\:\; 2\:\; 3\:\; 4\:} $. At this time, the sequence is fully sorted. Translated by ChatGPT 5