If you try to manage the first \(i\) elements with sets or arrays and check if, for every output, each non-negative integer appears in those terms, it won’t finish in time because there is a case where at least \(O(n^2)\) time is required in this way.

However, considering the property that, as \(i\) increases, the number of kinds of integers added also increases, we can see that the answer increases (does not decrease) as \(i\) increases.

Therefore, when finding the answer for an \(i\), it is sufficient to find the minimum value more than or equal to the answer for \(i-1\) which does not appear in the integers added so far. Try checking each value in the increasing order (*), and break from the loop when found. The number of operation (*) required is \(O(N)\) times in total.

The problem can be solved in a total of \(O(N)\) time if you implement (*) with an array, or \(O(N log N)\) time if you implement (*) with a set.

Sample code in C++

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
int t[210000];
int main(){
	int a;scanf("%d",&a);
	int at=0;
	for(int i=0;i<a;i++){
		int s;scanf("%d",&s);
		t[s]++;
		while(t[at]){
			at++;
		}
		printf("%d\n",at);
	}
}