A6418 | 「USACO 2018.12 Platinum」Sort It Out

**题目来自 [USACO 2018 December Contest, Platinum](http://usaco.org/index.php?page=dec18results) Problem 2. [Sort It Out](http://usaco.org/index.php?page=viewproblem2&cpid=865)**

FJ 有 $N$ 头奶牛（分别用 $1\ldots N$ 编号）排成一行。FJ 喜欢他的奶牛以升序排列，不幸的是现在她们的顺序被打乱了。在过去 FJ 曾经使用一些诸如「冒泡排序」的开创性的算法来使他的奶牛排好序，但今天他想偷个懒。取而代之，他会每次对着一头奶牛叫道「按顺序排好」。当一头奶牛被叫到的时候，她会确保自己在队伍中的顺序是正确的（从她的角度看来）。只要有一头紧接在她右边的奶牛的编号比她小，她们就交换位置。然后，只要有一头紧接在她左边的奶牛的编号比她大，她们就交换位置。这样这头奶牛就完成了「按顺序排好」，在这头奶牛看来左边的奶牛编号比她小，右边的奶牛编号比她大。

FJ 想要选出这些奶牛的一个子集，然后遍历这个子集，依次对着每一头奶牛发号施令（按编号递增的顺序），重复这样直到所有 $N$ 头奶牛排好顺序。例如，如果她选出了编号为 $\{2,4,5\}$ 的奶牛的子集，那么他会喊叫奶牛 $2$，然后是奶牛 $4$，然后是奶牛 $5$。如果 $N$ 头奶牛此时仍未排好顺序他会再次对着这几头奶牛喊叫，如果有必要的话继续重复。

由于 FJ 不确定哪些奶牛比较专心，他想要使得这个子集最小。此外，他认为 $K$ 是个幸运数字。请帮他求出满足重复喊叫可以使得所有奶牛排好顺序的最小子集之中字典序第 $K$ 小的子集。

我们称 $\{1,\ldots ,N\}$ 的一个子集 $S$ 在字典序下小于子集 $T$，当 $S$ 的所有元素组成的序列（按升序排列）在字典序下小于T的所有元素组成的序列（按升序排列）。例如，$\{1,3,6\}$ 在字典序下小于 $\{1,4,5\}$。

输入的第一行包含一个整数 $N$（$1\le N\le 10^5$）。第二行包含一个整数 $K$（$1\le K\le 10^{18}$）。第三行包含 $N$ 个空格分隔的整数，表示从左到右奶牛的编号。

保证存在至少 $K$ 个符合要求的子集。

第一行输出最小子集的大小。接下来输出字典序第 $K$ 小的最小子集中奶牛的编号，每行一个数，升序排列。