Mettere in ordine

FJ ha $n$ mucche (con ID distinti 1, \ldots, n) allineate in fila. A FJ piace che le sue mucche siano ordinate in ordine crescente di ID, ma sfortunatamente al momento sono disordinate. Sebbene in passato FJ abbia usato algoritmi rivoluzionari come il "bubble sort" per ordinare le sue mucche, oggi si sente piuttosto pigro. Invece, urlerà a mucche specifiche, una alla volta, di "mettersi in ordine". Quando viene chiamata, una mucca si assicura di non essere fuori posto (dal suo punto di vista). Finché la mucca immediatamente alla sua destra ha un ID più piccolo, si scambiano di posto. Poi, finché la mucca immediatamente alla sua sinistra ha un ID più grande, si scambiano di posto. Dopo di che, la mucca ha finito di "mettersi in ordine": la mucca alla sua sinistra ha un ID più piccolo, e la mucca alla sua destra ha un ID più grande.

FJ vuole scegliere un sottoinsieme di mucche e poi percorrerlo, chiamando ciascuna mucca a turno (in ordine crescente di ID), più e più volte finché tutte le $n$ mucche non sono ordinate. Per esempio, se sceglie il sottoinsieme di mucche con ID \{2, 4, 5\}, chiamerà la mucca $2$, poi la mucca $4$, e poi la mucca $5$. Se le $n$ mucche non sono ancora ordinate, chiamerà di nuovo le stesse mucche, più e più volte, quante volte sia necessario.

Poiché FJ non è sicuro di quali mucche stiano prestando attenzione, vuole minimizzare la dimensione di questo sottoinsieme. Inoltre, FJ considera il numero $k$ molto fortunato. Aiutalo a trovare il $k$-esimo sottoinsieme più piccolo in ordine lessicografico, tra quelli di dimensione minima, tale che chiamare ripetutamente le sue mucche porti infine all'ordinamento di tutte le mucche.

Un sottoinsieme $S$ di \{1, \ldots, n\} è lessicograficamente più piccolo di un sottoinsieme $T$ se la lista degli elementi di $S$ (in ordine crescente) è lessicograficamente più piccola della lista degli elementi di $T$ (in ordine crescente). Per esempio, \{1, 3, 6\} è lessicograficamente più piccolo di \{1, 4, 5\}.