Ordénense Solas

FJ tiene $n$ vacas (con IDs distintos 1, \ldots, n) alineadas en una fila. A FJ le gusta que sus vacas estén ordenadas en orden creciente de ID, pero desafortunadamente ahora mismo están desordenadas. Aunque en el pasado FJ ha usado algoritmos revolucionarios como el "bubble sort" para ordenar a sus vacas, hoy se siente bastante perezoso. En su lugar, le gritará a vacas específicas, una a la vez, para que "se ordenen solas". Cuando se le grita, una vaca se asegura de no estar desordenada (desde su punto de vista). Mientras la vaca inmediatamente a su derecha tenga un ID menor, intercambian lugares. Luego, mientras la vaca inmediatamente a su izquierda tenga un ID mayor, intercambian lugares. Después de eso, la vaca termina de "ordenarse": la vaca a su izquierda tiene un ID menor, y la vaca a su derecha tiene un ID mayor.

FJ quiere elegir un subconjunto de vacas y luego recorrer este subconjunto, gritándole a cada vaca por turno (en orden creciente de ID), una y otra vez hasta que las $n$ vacas estén ordenadas. Por ejemplo, si elige el subconjunto de vacas con IDs \{2, 4, 5\}, le gritará a la vaca $2$, luego a la vaca $4$, y luego a la vaca $5$. Si las $n$ vacas aún no están ordenadas, les gritará a las mismas vacas una y otra vez, tantas veces como sea necesario.

Como FJ no está seguro de qué vacas están prestando atención, quiere minimizar el tamaño de este subconjunto. Además, FJ considera que el número $k$ es muy afortunado. Ayúdalo a encontrar el $k$-ésimo subconjunto lexicográficamente más pequeño de tamaño mínimo tal que gritarle repetidamente a sus vacas eventualmente resulte en que todas las vacas queden ordenadas.

Un subconjunto $S$ de \{1, \ldots, n\} es lexicográficamente menor que un subconjunto $T$ si la lista de elementos de $S$ (en orden creciente) es lexicográficamente menor que la lista de elementos de $T$ (en orden creciente). Por ejemplo, \{1, 3, 6\} es lexicográficamente menor que \{1, 4, 5\}.