← 返回题目列表

Codeforces · 993/E

E. 尼基塔和订单统计

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

Nikita 喜欢顺序统计任务,例如,他可以轻松地在数组的一段上按升序找到第 $$$k$$$ 个数字。但现在 Nikita 想知道一个数组有多少个段,使得给定的数字 $$$x$$$ 是该段上按升序排列的第 $$$k$$$ 个数字。换句话说,您应该找到给定数组的段数,使得该段中恰好有 $$$k$$$ 个数字小于 $$$x$$$。

Nikita 希望获得从 $$$0$$$ 到 $$$n$$$ 的每个 $$$k$$$ 的这个问题的答案,其中 $$$n$$$ 是数组的大小。

输入

第一行包含两个整数 $$$n$$$ 和 $$$x$$$ $$$(1 \le n \le 2 \cdot 10^5, -10^9 \le x \le 10^9)$$$。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ - 给定数组。

输出

打印 $$$n+1$$$ 整数,其中第 $$$i$$$ 个数字是 Nikita 的 $$$k=i-1$$$ 问题的答案。

示例

输入 #1

5 3
1 2 3 4 5

输出 #1

6 5 4 0 0 0

输入 #2

2 6
-5 9

输出 #2

1 2 0

输入 #3

6 99
-1 -1 -1 -1 -1 -1

输出 #3

0 6 5 4 3 2 1