Отсортируй
У ФД есть n коров (пронумерованных 1..n), выстроенных в ряд. ФД любит, чтобы его коровы сортировались по возрастанию, но, к сожалению, в настоящее время они не упорядочены. Если в прошлом ФД использовал новаторские алгоритмы, такие как «сортировка пузырьком», чтобы сортировать своих коров, то сегодня он чувствует себя довольно ленивым. Вместо этого он будет кричать на конкретную корову, по одной, чтобы «сортировать». Когда на нее кричат, корова уверена что она неотсортирована в строю (с ее точки зрения). Пока справа от нее есть корова с меньшим ID, они меняются местами. Затем, пока слева от нее находится корова с большим ID, они меняются местами. Наконец, корова «отсортировалась», после чего у коровы слева от нее будет меньший ID, а у коровы справа — больший ID.
ФД хочет выбрать подмножество коров, а затем пройтись по этому подмножеству, крича на каждую из них по очереди (в порядке возрастания ID), снова и снова, пока все n коров не будут отсортированы. Например, если он выберет подмножество коров с идентификаторами {2, 4, 5}, то он будет кричать на корову 2, а затем на корову 4, а затем на корову 5. Если n коров все еще не отсортированы, он будет кричать на этих же коров снова и снова, по мере необходимости.
Поскольку ФД не уверен, какие коровы обращают на него внимание, он хочет минимизировать размер этого подмножества. Кроме того, ФД считает, что число k очень удачное. Помогите ему найти k-е лексикографически наименьшее подмножество минимального размера, чтобы многократное кричание на них в конце концов привело к сортировке всех коров.
Подмножество S из {1,..., n} называется лексикографически меньшим, чем подмножество T, если список элементов в S (в порядке возрастания) лексикографически меньше, чем список элементов в T (в порядке возрастания). Например, {1, 3, 6} лексикографически меньше, чем {1, 4, 5}.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 10^5). Вторая строка содержит одно целое число k (1 ≤ k ≤ 10^18). Третья строка содержит n целых чисел, представляющих номера коров слева направо.
Гарантируется, что существует не менее k допустимых подмножеств.
Выходные данные
Первая строка должна содержать размер минимального подмножества. Остальные строки должны содержать идентификаторы коров из k-го лексикографически наименьшего подмножества минимального размера, по одному идентификатору в строке, перечисленные в порядке возрастания.
Пример
Начнем с массива 4213. После того, как ФД накричит на корову с ID 1, массив будет 1423. Когда ФД кричит на корову с ID 4, массив будет 1234. В этот момент массив сортируется.