有一个互联网电子邮件群组。消息会发送给群组中的所有成员，且不会有两条消息在同一时间发送。

在某人发送消息之前，他们会阅读截至该时刻为止的所有未读消息。每位发送者在发送消息的瞬间也会阅读自己发送的消息。因此，一个人的未读消息恰好是该人最后一次发送消息之后所发送的所有消息的集合。

每当有一条消息被发送时，请计算所有群组成员的未读消息总数。

输入格式

输入的第一行包含两个整数 $n$ ($1 \le n \le 10^9$) 和 $m$ ($1 \le m \le 1,000$)，其中 $n$ 是群组中的人数，$m$ 是发送的消息总数。群组成员的编号为 $1$ 到 $n$。

接下来的 $m$ 行，每行包含一个整数 $s$ ($1 \le s \le n$)，表示该消息的发送者。这些行按时间顺序排列。

输出格式

输出 $m$ 行，每行包含一个整数，表示在每条消息发送后，所有群组成员的未读消息总数。

样例

样例输入 1

2 4
1
2
1
2

样例输出 1

1
1
1
1

样例输入 2

3 9
1
2
3
2
1
3
3
2
1

样例输出 2

2
3
3
4
3
3
5
4
3