それぞれの出力をするために最初の \(i\) 項を set や配列などで管理し、\(0\) から順にこれらの項に登場するか確認する方法では、少なくとも \(O(n^2)\) 以上かかるケースが存在し、これでは間に合いません。

しかし、\(i\) が大きくなるにつれ追加された整数の種類数が徐々に増えていくことを考えると、 \(i\) が大きくなるにつれ答えも増加すること(減少しないこと)が考えられます。

よって、ある \(i\) に対する答えを求めたいときは、 \(i-1\) について求めた答え以上の値で、今まで追加した整数の中に登場しない最小の値を求めれば良いです。これは値を小さい順に一つずつ試していき(※)、見つけたところでループを抜けるという実装でも合計で \(O(N)\) 回の(※)で済みます。

配列で (※) を実装すれば \(O(N)\) 、setで (※) を実装すれば \(O(N log N)\) でこの問題全体が解けます。

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);
	}
}