Nikita likes tasks on order statistics, for example, he can easily find the -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 is the -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 numbers of this segment which are less than .
Nikita wants to get answer for this question for each from to , where is the size of the array.
Input
The first line contains two integers and .
The second line contains integers — the given array.
Output
Print integers, where the -th number is the answer for Nikita’s question for .
v1.5.2