题目描述

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

他有一叠特制的纸牌，共有 $n$ 张，从上到下的点数依次为 $a_1, a_2, \ldots, a_n$。每张牌的点数都是 $1$ 到 $m$ 之间的整数，且每种点数都出现至少一次。

小 Z 将进行 $n$ 局相互独立的游戏。每局开始前，他会将所有牌按原顺序放回牌堆，并清空桌面。在第 $i\ (1 \le i \le n)$ 局中，他跳过前 $i-1$ 张牌，依次打出第 $i$ 张到第 $n$ 张牌，这些牌的点数依次为 $a_i, a_{i+1}, \ldots, 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, \ldots, m$，在所有 $n$ 局游戏中，有多少局结束时桌面上留有点数为 $i$ 的牌。

输入格式

输入的第一行包含两个正整数 $n, m$，分别表示牌的数量和点数种类数。

输入的第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出一行 $m$ 个非负整数，其中第 $i$ 个整数表示在所有 $n$ 局游戏中，有多少局结束时桌面上留有点数为 $i$ 的牌。

样例 1

4 3
1 2 1 3

3 1 4

样例 2

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

10 3 3

说明

样例 1 解释：第 1 局结束时桌面是 1, 3；第 2 局是 2, 1, 3；第 3 局是 1, 3；第 4 局是 3。所以点数 1 留在 3 局里（第 1、2、3 局），点数 2 留在 1 局里，点数 3 留在全部 4 局里。

数据范围

对于所有测试数据，均有：$2 \le n \le 5 \times 10^5$，$1 \le m \le 3 \times 10^5$；$1 \le a_i \le m$；每种点数都出现至少一次。

• 特殊性质 A：$a_1 \le a_2 \le \cdots \le a_n$。
• 特殊性质 B：至多存在 $4999$ 个 $i\ (1 \le i \le n-1)$ 满足 $a_i \ne a_{i+1}$。

本题需要文件读写：输入文件 card.in，输出文件 card.out。

来源：CSP-J 2026 第二轮 T4。本 OJ 的测试数据为按题面测试点表自造，不是官方数据。