Sort It Out

FJ has $n$ cows (with distinct IDs 1, \ldots, n) lined up in a row. FJ likes his cows to be sorted in increasing order of ID, but unfortunately they are currently out of order. Although in the past FJ has used groundbreaking algorithms such as "bubble sort" to sort his cows, today he is feeling quite lazy. Instead, he will yell at specific cows, one at a time, to "sort it out". When yelled at, a cow makes sure she is not out of order (from her point of view). While the cow immediately to her right has a smaller ID, they swap places. Then, while the cow immediately to her left has a larger ID, they swap places. After that, the cow is done "sorting it out": the cow to her left has a smaller ID, and the cow to her right has a larger ID.

FJ wants to choose a subset of cows and then go through this subset, yelling at each cow in turn (in increasing order of ID), again and again until all $n$ cows are sorted. For instance, if he chooses the subset of cows with IDs \{2, 4, 5\}, he will yell at cow $2$, then at cow $4$, and then at cow $5$. If the $n$ cows are still not sorted, he will yell at the same cows again and again, as many times as necessary.

Since FJ is not sure which cows are paying attention, he wants to minimize the size of this subset. Furthermore, FJ considers the number $k$ to be very lucky. Help him find the $k$-th lexicographically smallest subset of minimum size such that repeatedly yelling at its cows eventually results in all cows being sorted.

A subset $S$ of \{1, \ldots, n\} is lexicographically smaller than a subset $T$ if the list of elements of $S$ (in increasing order) is lexicographically smaller than the list of elements of $T$ (in increasing order). For instance, \{1, 3, 6\} is lexicographically smaller than \{1, 4, 5\}.