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

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

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

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

输入的第二行包含 n 个正整数 a_1, a_2, \cdots, a_n，依次表示小 Z 的牌从上到下的点数。

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

样例 1 解释：四局结束时的桌面分别是 (1, 3)、(2, 1, 3)、(1, 3)、(3)。于是点数 1 留在 3 局的桌面上（第 1、2、3 局），点数 2 留在 1 局上（第 2 局），点数 3 在 4 局里都在（它每次都是最后被放上去的）。

数据范围

• 2 \le n \le 5 \times 10^5，1 \le m \le 3 \times 10^5；

• 1 \le a_i \le m，且每种点数都至少出现一次。

测试点构成（共 25 个测试点）

提示：先盯住第 i 局的第一张牌，也就是点数 v = a_i。

• 如果 v 在 i 之后还会出现，设下一次出现在 nxt。因为 v 是这一局最早放上去的牌，它一直在桌面的最左端；到第 nxt 张牌时再打一张 v，会把它和它右边的所有牌一起收走，桌面被清空后又只放上一张 v。此时局面与「直接从第 nxt 局开始」一模一样，所以第 i 局的终局面等于第 nxt 局的终局面。

• 如果 v 在 i 之后再没出现，那它永远不会被收走（它左边没有牌了），所以它会一直留在桌面上，而其余牌的结局与第 i+1 局完全相同。

把 L(v) 记为点数 v 在整个序列中最后一次出现的位置，上面两条合起来就是

\text{deck}(i) = [\,a_i\,] + \text{deck}(L(a_i) + 1)

也就是说，沿着 "从 i 跳到 L(a_i) + 1" 这条链一直往右跳，链上每个落点上的点数拼起来就是第 i 局结束时的桌面（从左到右）。因为跳一步就到 L(v) + 1，一条链上不会出现两次相同的点数。

于是问题变成：对每个位置 p，数一数有多少个起点 i 的链会经过它，记为 A_p。因为「起点就是 p 自己」算一个，再把所有「下一步落在 p」的位置 r 的 A_r 都加过来，即

A_p = 1 + \sum_{r:\ L(a_r)+1\,=\,p} A_r

而 L(a_r) + 1 > r，所以按 p 从小到大递推即可。最后 \text{ans}_v = \sum_{p:\ a_p = v} A_p，因为一条链上同一点数只会出现一次，不会重复计数。