问题描述

高桥君接收到一个长度为 $N$ 的由整数 $1$ 到 $C$ 组成的数列 $\\{a_N\\} = \\{a_1,a_2, ...,a_N\\}$，他需要计算对于每个整数 $k$ （$1 ≤ k ≤ C$），存在满足 $1 ≤ l ≤ r ≤ N$ 且 $a_i = k$（$l ≤ i ≤ r$）的 $(l,r)$ 组合的数量。

请编写一个程序来验证高桥君的行为。

输入

输入通过标准输入给出，具体格式如下：

$N$ $C$ $a_1$ $a_2$ … $a_N$

• 第 $1$ 行为数列的长度 $N (1 ≤ N ≤ 10^5)$ 和数列的最大值 $C (1 ≤ C ≤ N)$，以空格分隔。
• 第 $2$ 行为高桥君接收到的数列，包含 $N$ 个数字，以空格分隔。保证 $1 ≤ a_i ≤ C$。同时保证对于 $1$ 到 $C$ 之间的每个整数 $k$，都存在一个 $i$ 使得 $a_i = k$。

部分分

本问题包含部分分。

• 在 $30$ 个测试用例中，满足 $1≤C≤20$。

输出

对于每个整数 $i (1 ≤ i ≤ C)$，在第 $i$ 行输出 $\\{a_N\\}$ 中包含整数 $i$ 的连续子序列的数量。

请勿忘记输出换行符。另外，每行末尾不要有多余的空格。

示例1

4 2
1 2 2 1

输出1

7
8

满足以 $1$ 开头的连续子序列有 $(l,r)=(1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4)$

满足以 $2$ 开头的连续子序列有 $(l,r)=(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4)$。

示例2

4 4
1 4 2 3

输出2

4
6
4
6

示例3

5 1
1 1 1 1 1

输出3

15