UT Invitational Programming Contest Fall 2019

Start

2019-11-23 19:00 UTC

UT Invitational Programming Contest Fall 2019

End

2019-11-24 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -190 days 1:54:21

Time elapsed

5:00:00

Time remaining

0:00:00

Problem F
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$.

Input

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

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