Buttons

There is a toy with $n+1$ buttons. Above each of the first $n$ buttons there is a small counter, and every counter starts at $0$. Pressing a button increases the counter above it by $1$.

Button number $n+1$ behaves in a special way. When it is pressed, all $n$ counters are set to the largest value that has ever appeared on any counter of the toy so far. For example, if $n = 5$ and the counters currently show $0$, $0$, $1$, $2$, $0$, then pressing button $n+1$ (button $6$) makes every counter show $2$.

Given the order in which the buttons were pressed, determine the value shown by each counter after all operations are finished.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$): the number of counters on the toy and the number of operations. The second line contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_i \le n+1$): the numbers of the buttons that were pressed, in order.

Print $n$ integers on a single line, separated by single spaces: the values shown by the counters, in order, after all operations are finished.