分数: 400 点
问题陈述
有一副牌,包括 N 面朝下的牌,其整数为 上面写着 1 通过 N 。 上的整数 i从顶部算起的第一张牌是 P_i.
使用这副牌,你将执行 N 移动,每个移动包含以下步骤:
- 从牌堆中抽出最上面的牌。 让 X 是上面写的整数。
- 将抽取的牌面朝上堆叠到桌面上面朝上最上面的牌中整数最小的牌上,且整数大于或等于 上面写着 X 。 如果桌上没有这样的牌,则将抽出的牌正面朝上放在桌上,不要将其堆叠到任何牌上。
- 那么,如果有一堆由 K 桌子上正面朝上的牌,吃掉所有这些牌。 吃掉的牌全部从桌子上消失。
对于每张卡片,找出哪张卡片是 N 移动吃掉它。 如果直到最后卡片都没有被吃掉,请报告这一事实。
约束
- 输入中的所有值都是整数。
- 1 \le K \le N \le 2 \times 10^5
- P 是一个排列 (1,2,\dots,N) (即通过重新排列获得的序列 (1,2,\dots,N)).
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \dots P_N
输出
打印
您选择的 N 行。
的 i- 第行 (1 \le i \le N) 应使用整数描述卡
上面写着 i 。 具体来说,
- 如果该卡带有 上面写着 i 是在吃的 x第一步,打印 x;
- 如果该卡在任何一步中都没有被吃掉,则打印 -1.
示例输入 1
5 2 3 5 2 1 4
示例输出 1
4 3 3 -1 4
在此输入中, P=(3,5,2,1,4) 和 K=2.
- 在 1-st 动作,该牌带有 写有 3 的卡片正面朝上放在桌子上,不要叠放在任何卡片上。
- 在 2-nd 动作,该牌带有 5 的卡片正面朝上放在桌子上,不要叠放在任何卡片上。
- 在 3-rd 动作,该牌带有
上面写有 2 ,正面朝上堆叠到卡片上, 3 。
- 现在有一堆由 K=2 面朝上的牌,上面有 从上往下写的是 2 和 3 ,所以这些卡牌被吃掉了。
- 在 4第一步,带有 1 ,正面朝上堆叠到卡片上, 5 。
- 现在有一堆由 K=2 面朝上的牌,上面有 从上往下写的是 1 和 5 ,所以这些卡牌被吃掉了。
- 在 5第一步,带有 4 的卡片正面朝上放在桌子上,不要叠放在任何卡片上。
- 该卡带有 上面写着 4 直到最后都没有被吃掉。
示例输入 2
5 1 1 2 3 4 5
示例输出 2
1 2 3 4 5
If K=1,每张牌在一次移动中放在桌子上后立即被吃掉。
示例输入 3
15 3 3 14 15 9 2 6 5 13 1 7 10 11 8 12 4
示例输出 3
9 9 9 15 15 6 -1 -1 6 -1 -1 -1 -1 6 15