# 描述

Nikita likes tasks on order statistics, for example, he can easily find the k-th number in increasing order on a segment of an array. But now Nikita wonders how many segments of an array there are such that a given number $x$ is the $k$-th number in increasing order on this segment. In other words, you should find the number of segments of a given array such that there are exactly $k$ numbers of this segment which are less than $x$.

Nikita wants to get answer for this question for each k from $0$ to $n$, where $n$ is the size of the array.

## Input

The first line contains two integers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5, -10^9 \le x \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the given array.

## Output

Print $n + 1$ integers, where the $i$-th number is the answer for Nikita’s question for $k = i - 1$.

Input Output

# 思路

• 首先考虑前缀子段中小于$x$的数的个数，记作$p[i]$。
• 对$p[i]$计数，记作$r$。那么$ans[d] = \sum\limits_{j - i = d} r[i] * r[j]$
• 适当变换一下，令$v[i] = r[n - i]$，则$$ans[d] = \sum\limits_{i + j = n + d} r[i] * v[j]$$
• 然后上面这个式子就可以用FFT来求了。
• 当然$k = 0$的时候需要去重和去序。
• 数据范围告诉我们答案最大会到$10 ^ {10}$，所以要使用long long

0%