D - 高橋くんと数列 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんは長さ N の 1 から C の整数からなる数列 \{a_N\} = \{a_1,a_2, ...,a_N\} を受け取って、 1 以上 C 以下のそれぞれの整数について、その数を1つでも含む連続する部分列の数を返す機械です。

より正確には、 1 以上 C 以下の整数 k について、 1 ≦ l ≦ r ≦ N となるような l,r で、 a_i = k かつ l≦ i ≦ r を満たすものが存在するような (l,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 に対し、 a_i = kを満たす i が存在することが保証される。

部分点

この問題には部分点が設定されている。

  • 30 点分のテストケースにおいて、1≦C≦20 を満たす。

出力

i (1 ≦ i ≦ C) 行目には、\{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