← 返回题目列表

AtCoder · indeednow_2015_qualb_4

D. 高桥君和数列

中文机器翻译题面 查看原题

問題文

高桥同学接受一个长度为 N 的 1 它们的编号最大为 C 的整数数列 \{a_N\} = \{a_1,a_2, ...,a_N\} ,并且 1 以上 C 是一个机械装置,它会对每个不超过该值的整数,返回至少包含该整数的连续子序列的数量。

更准确地说, 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