Навести лад

У ФД є $n$ корів (з різними ідентифікаторами 1, \ldots, n), що вишикувані в ряд. ФД подобається, коли його корови відсортовані за зростанням ідентифікатора, але, на жаль, зараз вони стоять не по порядку. Хоча в минулому ФД використовував революційні алгоритми на кшталт "сортування бульбашкою" для сортування своїх корів, сьогодні йому доволі ліньки. Натомість, він буде по черзі покрикувати на конкретних корів, по одній, щоб вони "навели лад". Коли на корову покрикують, вона переконується, що вона не стоїть не на своєму місці (з її точки зору). Доки корова безпосередньо справа від неї має менший ідентифікатор, вони міняються місцями. Потім, доки корова безпосередньо зліва від неї має більший ідентифікатор, вони міняються місцями. Після цього корова закінчує "наводити лад": корова зліва від неї має менший ідентифікатор, а корова справа від неї має більший ідентифікатор.

ФД хоче вибрати підмножину корів, а потім пройтися по цій підмножині, покрикуючи на кожну корову по черзі (у порядку зростання ідентифікатора), знову і знову, доки всі $n$ корів не будуть відсортовані. Наприклад, якщо він вибере підмножину корів з ідентифікаторами \{2, 4, 5\}, він покричить на корову $2$, потім на корову $4$, а потім на корову $5$. Якщо $n$ корів все ще не відсортовані, він покричить на тих самих корів знову і знову, стільки разів, скільки потрібно.

Оскільки ФД не впевнений, які корови уважні, він хоче мінімізувати розмір цієї підмножини. Крім того, ФД вважає число $k$ дуже щасливим. Допоможіть йому знайти $k$-ту лексикографічно найменшу підмножину мінімального розміру таку, що повторюване покрикування на її корів зрештою призводить до того, що всі корови виявляються відсортованими.

Підмножина $S$ множини \{1, \ldots, n\} є лексикографічно меншою за підмножину $T$, якщо список елементів $S$ (у порядку зростання) є лексикографічно меншим за список елементів $T$ (у порядку зростання). Наприклад, \{1, 3, 6\} є лексикографічно меншим за \{1, 4, 5\}.