Problem Description

Takahashi receives a sequence of length $ N $ consisting of integers from $ 1 $ to $ C $, denoted as $\{a_N\} = \{a_1, a_2, ..., a_N\}$, and returns the number of contiguous subsequences that contain at least one of each integer from $ 1 $ to $ C $.

More precisely, for each integer $ k $ from $ 1 $ to $ C $, Takahashi finds the number of pairs $ (l, r) $ such that $ 1 ≦ l ≦ r ≦ N $ and there exists an $ i $ with $ l ≦ i ≦ r $ where $ a_i = k $.

Note that even if the contents of the contiguous subsequences are the same, different pairs $ (l, r) $ are considered different. Write a program to verify Takahashi's operation.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains the length of the sequence $N\ (1 ≦ N ≦ 10^5)$ and the maximum value of the sequence elements $C\ (1 ≦ C ≦ N)$, separated by spaces.
• The second line contains $ N $ numbers representing the elements of the sequence received by Takahashi, separated by spaces. It is guaranteed that $ 1 ≦ a_i ≦ C $. Additionally, for every integer $ k $ from $ 1 $ to $ C $, there exists an $ i $ such that $ a_i = k $.

Output Format

For each $i\ (1 ≦ i ≦ C)$, output the number of contiguous subsequences that contain $ i $.

Do not forget the newline at the end of the output. Also, do not add extra spaces at the end of each line.

Sample Input and Output

Sample Input #1

4 2
1 2 2 1

Sample Output #1

7
8

Sample Input #2

4 4
1 4 2 3

Sample Output #2

4
6
4
6

Sample Input #3

5 1
1 1 1 1 1

Sample Output #3

15

Notes/Hints

Partial Points

This problem has partial points.

• For $ 30 $ points, $ 1 ≦ C ≦ 20 $.

Sample Explanation 1

Contiguous subsequences containing $ 1 $ are: $ (l, r) = (1,1), (1,2), (1,3), (1,4), (2,4), (3,4), (4,4) $.
Contiguous subsequences containing $ 2 $ are: $ (l, r) = (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4) $.

见题面 Input 部分

见题面 Output 部分