Leonard and MEX

0

0 votes
Easy
Problem

Wolowitz has given Leonard a problem to solve. The problem consists of a sequence of N integers and asks if we insert all elements of this sequence into a set, what will be the MEX of this set. MEX of a set is the smallest non-negative integer which is not present in that set. Leonard easily solves this problem. Seeing this, Wolowitz modifies the problem and comes up with an even harder problem. This one asks if we take the same sequence of N integers and start from leftmost integer and one-by-one insert each element into a set, then calculate the MEX at each step.

Leonard being just an "Experimental physicist" is unable to solve this problem and has asked for your help.

Input Format:

First line contains a number N denoting the length of sequence.

Second line contains N numbers denoting the sequence.

Output Format:

Output N integers separated by space denoting the required answer.

Constraints:

1N106

0A[i]109

Sample Input
7
3 5 3 1 9 0 2
Sample Output
0 0 0 0 0 2 4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

After 1st number is inserted, set is {3}. It's MEX is 0.

After 2nd number is inserted, set is {3, 5}. It's MEX is 0.

After 3rd number is inserted, set is {3, 5}. Here, 3 is written only once as set only contains distinct values. It's MEX is 0.

After 4th number is inserted, set is {1, 3, 5}. It's MEX is 0.

After 5th number is inserted, set is {1, 3, 5, 9}. It's MEX is 0.

After 6th number is inserted, set is {0, 1, 3, 5, 9}. It's MEX is 2.

After 7th number is inserted, set is {0, 1, 2, 3, 5, 9}. It's MEX is 4.

Editor Image

?