配点 : 1200 点
問題文
如果是良好的序列,高桥君拥有长度为 N 序列 使用 A 。 高桥君A 开始玩找最长递增子序列。 A 的最长递增子序列是,A 的子序列,并且是严格单调递增的序列中,表示最长的序列。 高桥君认为, 仅仅寻找A 的最长递增子序列太无聊了, 于是决定在A 的最长递增子序列中,按照字典顺序寻找 第 K 个序列。 另外,即使取出的元素位置不同,只要作为数列相同的子序列,不再区分。
但是,高桥君中途累了就睡着了。
请代替高桥君,
编写程序输出A 的最长递增子序列中,按字典顺序的第 K 个序列。
如果不存在这样的序列,
按照空格分隔输出第None 。
制約
- 所有输入均为整数
- 1 \leq N \leq 300,000
- 1 \leq K \leq 10^{18}
- 1 \leq A_i \leq 10^9
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 ... A_N
出力
A 的最长递增子序列中,按字典顺序的第 K 个序列。
如果不存在这样的序列,None 。
入力例 1
6 2 3 6 5 1 2 7
出力例 1
3 5 7
A 的最长递增子序列如下的 3 方法有很多。
- [1,2,7]
- [3,5,7]
- [3,6,7]
个按字典顺序排列的序列。 2 第几的东西是,[3,5,7] 。 求放置超过
入力例 2
4 2 1 1 2 2
出力例 2
None
A 的最长递增子序列有,[1,2] 可以得到第 1 种方式,所以,None 。
入力例 3
20 1000 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19
出力例 3
2 4 6 8 10 11 13 16 18 20