Dominant Conversations

Whenever people get together, there are some people who dominate regions of the conversation. We are given a record of a $N$-second long conversation which details who was talking at each second (people talk in second-long intervals). For each of $K$ people, your job is to find out the number of regions of the conversation they dominate. A region is a chunk of time from second $i$ to second $j$ inclusive, with $i \leq j$, and it is dominated by person $k$ if more that half of the entries in the range $[i,j]$ of the record are $k$.

The first line contains space-separated integers $n,k$ such that $1 \leq n,k \leq 10^6$. The second line contains $n$ space separated integers $a_ i$, the entries in the record. $0 \leq a_ i < k$

Output $k$ lines, the $i$th of which denotes the number of regions dominated by the $i$th person ($0$-indexed).

Sample Input 1 | Sample Output 1 |
---|---|

5 1 0 0 0 0 0 |
15 |

Sample Input 2 | Sample Output 2 |
---|---|

5 2 0 1 1 1 1 |
1 13 |