← 返回题目列表

AtCoder · yahoo_procon2017_final_d

D. 第K长递增子序列

中文机器翻译题面 查看原题

配点 : 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