D. 纸牌游戏 / card
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

小 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$$$ 的牌。

Input

从标准输入读入数据。

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

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

Output

输出到标准输出。

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

Examples
Input
4 3
1 2 1 3
Output
3 1 4
Input
10 3
3 1 2 1 3 2 3 1 2 1
Output
10 3 3
Note

补充样例文件可从原题页面的附件下载：https://www.luogu.com.cn/problem/P17830。

样例 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$$$ 局。

样例 3

见题目目录下的 card/3.in 与 card/3.ans。

该样例满足测试点 $$$4\sim 6$$$ 的约束条件。

样例 4

见题目目录下的 card/4.in 与 card/4.ans。

该样例满足测试点 $$$7\sim 9$$$ 的约束条件。

样例 5

见题目目录下的 card/5.in 与 card/5.ans。

该样例满足测试点 $$$15\sim 17$$$ 的约束条件。

样例 6

见题目目录下的 card/6.in 与 card/6.ans。

该样例满足测试点 $$$21,22$$$ 的约束条件。

数据范围

对于所有测试数据，均有：

  • $$$2\le n\le 5\times 10^5$$$，$$$1\le m\le 3\times 10^5$$$；
  • 对于所有 $$$i$$$（$$$1\le i\le n$$$），均有 $$$1\le a_i\le m$$$；
  • 每种点数都出现至少一次，即对于所有 $$$i$$$（$$$1\le i\le m$$$），均存在 $$$j$$$（$$$1\le j\le n$$$）满足 $$$a_j=i$$$。
测试点编号$$$n\le$$$$$$m\le$$$特殊性质
$$$1\sim 3$$$$$$5$$$$$$2$$$无
$$$4\sim 6$$$$$$500$$$$$$200$$$无
$$$7\sim 9$$$$$$5000$$$$$$3000$$$A
$$$10\sim 12$$$$$$5000$$$$$$3000$$$无
$$$13,14$$$$$$2\times 10^5$$$$$$2$$$无
$$$15\sim 17$$$$$$2\times 10^5$$$$$$3000$$$B
$$$18,19$$$$$$2\times 10^5$$$$$$3000$$$无
$$$20$$$$$$2\times 10^5$$$$$$10^5$$$A
$$$21,22$$$$$$2\times 10^5$$$$$$10^5$$$无
$$$23\sim 25$$$$$$5\times 10^5$$$$$$3\times 10^5$$$无

特殊性质 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}$$$。

本题满分 100 分。官方测试点共 25 个，每个测试点 4 分，独立计分。展示样例中，与官方测试点完全相同的样例保留原测试点分值；其余样例不计分。