4514. 纸牌游戏

【题目描述】

小Z 正在玩一种单人纸牌游戏。

他有一叠特制的纸牌，共有n 张，从上到下的点数依次为a1 ,a2 ,...,an。每张牌的点数都是1 到m 之间的整数，且每种点数都出现至少一次。

小Z 将进行n 局相互独立的游戏。每局开始前，他会将所有牌按原顺序放回牌堆，并清空桌面。在第i (1 ≤ i ≤ n) 局中，他跳过前i − 1 张牌，依次打出第i 张到第n 张牌，这些牌的点数依次为a_i ,a_i+1,...,a_n。

桌面上的牌始终从左到右排成一行。打出一张点数为k 的牌时：

• 若桌面上没有点数为k 的牌，就将这张牌放在最右端；

•  否则，收走桌面上点数为k 的牌及其右侧的所有牌，再把这张牌放在最右端。被收走的牌在本局中不再使用。

由上述规则可知，任意时刻桌面上同一种点数的牌至多只有一张。

最后一张牌打出后，本局游戏结束。

例如，若桌面上从左到右的牌的点数依次为1 ,4 ,2，则打出一张点数为3 的牌后，桌面上从左到右的牌的点数依次为1 ,4 ,2 ,3。接着打出一张点数为4 的牌时，桌面上原来点数为4 的牌及其右侧的所有牌（点数依次为4 ,2 ,3）被收走，再把新打出的4 放在最右端，此时桌面上从左到右的牌的点数依次为1 ,4。你需要帮助小Z 依次求出，对于每个i = 1 ,2 ,...,m，在所有n 局游戏中，有多少局结束时桌面上留有点数为i 的牌。

【输入格式】

从文件card.in 中读入数据。

输入的第一行包含两个正整数n,m，分别表示牌的数量和点数种类数。输入的第二行包含n 个正整数a1 ,a2 ,...,an，依次表示小Z 的牌从上到下的点数。

【输出格式】

输出到文件card.out 中。输出一行m 个非负整数，其中第i (1 ≤ i ≤ m) 个整数表示在所有n 局游戏中，有多少局结束时桌面上留有点数为i 的牌。

【样例1输入】

4 3
1 2 1 3

【样例1输出】

3 1 4

【样例1说明】

对于第1 局游戏，小Z 依次打出点数为1 ,2 ,1 ,3 的牌：

1. 打出第1 张牌（点数为1）后，桌面上只有一张点数为1 的牌；

2. 打出第2 张牌（点数为2）后，桌面上从左到右的牌的点数依次为1 ,2；

3. 打出第3 张牌（点数为1）后，先收走桌面上点数为1 ,2 的两张牌，再放上新打出的1，桌面上只有一张点数为1 的牌；

4. 打出第4 张牌（点数为3）后，桌面上从左到右的牌的点数依次为1 ,3。

因此第1 局游戏结束时，桌面上从左到右的牌的点数依次为1 ,3。

对于第2 局游戏，小Z 依次打出点数为2 ,1 ,3 的牌，结束时桌面上从左到右的牌的点数依次为2 ,1 ,3。

对于第3 局游戏，小Z 依次打出点数为1 ,3 的牌，结束时桌面上从左到右的牌的点数依次为1 ,3。

对于第4 局游戏，小Z 仅打出一张点数为3 的牌，结束时桌面上只有一张点数为3 的牌。

因此，在全部4 局游戏中：

• 有3 局游戏结束时，桌面上留有点数为1 的牌，即第1 ,2 ,3 局；

• 有1 局游戏结束时，桌面上留有点数为2 的牌，即第2 局；

• 有4 局游戏结束时，桌面上留有点数为3 的牌，即全部4 局。

【样例2输入】

10 3
3 1 2 1 3 2 3 1 2 1

【样例2输出】

10 3 3

【数据规模与约定】

【来源】

在此键入。