C - Neq Min Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の数列 p_1, ... , p_N が与えられます。

各 i=1, 2, ..., N について、 0 以上の整数で p_1,...,p_i のいずれとも等しくない値のうち最小値を求めてください。

制約

  • 1 \leq N \leq 200,000
  • 0 \leq p_i \leq 200,000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
p_1 ... p_N

出力

合計 N 行出力せよ。

i 行目 (1 \leq i \leq N) には 0 以上の整数で p_1,...,p_i のいずれとも等しくない値のうち最小値を出力せよ。

入力例 1

4
1 1 0 2

出力例 1

0
0
2
3
  • 0 以上の整数で p_1=1 と等しくない最小値は 0 です。
  • 0 以上の整数で p_1=1, p_2=1 のいずれとも等しくない最小値は 0 です。
  • 0 以上の整数で p_1=1, p_2=1, p_3=0 のいずれとも等しくない最小値は 2 です。
  • 0 以上の整数で p_1=1, p_2=1, p_3=0, p_4=2 のいずれとも等しくない最小値は 3 です。

入力例 2

10
5 4 3 2 1 0 7 7 6 6

出力例 2

0
0
0
0
0
6
6
6
8
8

Score : 300 points

Problem Statement

Given is a number sequence of length N: p_1, ..., p_N.

For each i=1, 2, ..., N, find the minimum non-negative integer that is not equal to any of the numbers p_1, ..., p_i.

Constraints

  • 1 \leq N \leq 200,000
  • 0 \leq p_i \leq 200,000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
p_1 ... p_N

Output

Print N lines in total.

The i-th line (1 \leq i \leq N) should contain the minimum non-negative integer that is not equal to any of the numbers p_1, ..., p_i.

Sample Input 1

4
1 1 0 2

Sample Output 1

0
0
2
3
  • The minimum non-negative integer that is not equal to p_1=1 is 0.
  • The minimum non-negative integer that is not equal to any of p_1=1, p_2=1 is 0.
  • The minimum non-negative integer that is not equal to any of p_1=1, p_2=1, p_3=0 is 2.
  • The minimum non-negative integer that is not equal to any of p_1=1, p_2=1, p_3=0, p_4=2 is 3.

Sample Input 2

10
5 4 3 2 1 0 7 7 6 6

Sample Output 2

0
0
0
0
0
6
6
6
8
8