2020 South Central USA Regional Contest

Start

2021-03-06 10:00 CET

2020 South Central USA Regional Contest

End

2021-03-06 15:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -2 days 9:29:29

Time elapsed

5:00:00

Time remaining

0:00:00

Problem P
Unread Messages

There is a group of people in an internet email message group. Messages are sent to all members of the group, and no two messages are sent at the same time.

Immediately before a person sends a message, they read all their unread messages up to that point. Each sender also reads their own message the moment it is sent. Therefore, a person’s unread messages are exactly the set of messages sent after that person’s last message.

Each time a message is sent, compute the total number of unread messages over all group members.

Input

The first line of input contains two integers n (1n109) and m (1m1000), where n is the number of people in the group, and m is the number of messages sent. The group members are identified by number, 1 through n.

Each of the next m lines contains a single integer s (1sn), which is the sender of that message. These lines are in chronological order.

Output

Output m lines, each with a single integer, indicating the total number of unread messages over all group members, immediately after each message is sent.

Sample Input 1 Sample Output 1
2 4
1
2
1
2
1
1
1
1
Sample Input 2 Sample Output 2
3 9
1
2
3
2
1
3
3
2
1
2
3
3
4
3
3
5
4
3