叠牌游戏

题目描述

有一叠 $N$ 张背面朝上的卡片,上面分别写着 $1$ 到 $N$ 的整数。从上数第 $i$ 张卡片上的整数为 $P_i$。

使用这叠卡片,你将进行 $N$ 轮操作,每轮由以下步骤组成:

1. 从牌堆顶部抽出一张卡片。设其上的整数为 $X$。
2. 将抽出的卡片正面朝上,叠放到桌面上所有「顶端卡片写着大于等于 $X$ 的整数」的牌堆中,顶端整数最小的那一堆上。如果桌面上没有这样的牌堆,则把抽出的卡片正面朝上直接放在桌面上,不叠放到任何牌堆上。
3. 然后,如果桌面上存在由 $K$ 张正面朝上的卡片组成的牌堆,则吃掉该牌堆中的所有卡片。被吃掉的卡片全部从桌面上消失。

对每张卡片,求它是在第几轮被吃掉的。如果该卡片直到结束都未被吃掉,则输出 -1 以报告这一事实。

输入格式

输入按以下格式从标准输入给出:

N K
P_1 P_2 … P_N

输出格式

输出 $N$ 行。

第 $i$ 行($1 \le i \le N$)描述写着整数 $i$ 的卡片。具体来说:

• 如果写着 $i$ 的卡片在第 $x$ 轮被吃掉,输出 $x$;
• 如果该卡片在任何一轮都没有被吃掉,输出 $-1$。

样例

5 2
3 5 2 1 4

4
3
3
-1
4

在本输入中,$P=(3,5,2,1,4)$,$K=2$。

第 $1$ 轮,写着 $3$ 的卡片被正面朝上放在桌面上,没有叠放到任何牌堆上。

第 $2$ 轮,写着 $5$ 的卡片被正面朝上放在桌面上,没有叠放到任何牌堆上。

第 $3$ 轮,写着 $2$ 的卡片被正面朝上叠放到写着 $3$ 的卡片上。

此时,桌面上出现了由 $K=2$ 张正面朝上的卡片组成的牌堆,从上到下写着 $2$、$3$,因此这些卡片被吃掉。

第 $4$ 轮,写着 $1$ 的卡片被正面朝上叠放到写着 $5$ 的卡片上。

此时,桌面上出现了由 $K=2$ 张正面朝上的卡片组成的牌堆,从上到下写着 $1$、$5$,因此这些卡片被吃掉。

第 $5$ 轮,写着 $4$ 的卡片被正面朝上放在桌面上,没有叠放到任何牌堆上。

写着 $4$ 的卡片直到结束都没有被吃掉。

5 1
1 2 3 4 5

1
2
3
4
5

如果 $K=1$,每张卡片在放到桌面上后的一轮内就会被立即吃掉。

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

数据范围

• 输入中的所有值均为整数。
• $1 \le K \le N \le 2 \times 10^5$
• $P$ 是 $(1,2,\dots,N)$ 的一个排列(即将 $(1,2,\dots,N)$ 重新排列得到的序列)。