codeforces#P1364C. Ehab and Prefix MEXs

    ID: 31211 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>brute forceconstructive algorithmsgreedy*1600

Ehab and Prefix MEXs

Description

Given an array aa of length nn, find another array, bb, of length nn such that:

  • for each ii (1in)(1 \le i \le n) MEX({b1MEX(\{b_1, b2b_2, \ldots, bi})=aib_i\})=a_i.

The MEXMEX of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.

The first line contains an integer nn (1n1051 \le n \le 10^5) — the length of the array aa.

The second line contains nn integers a1a_1, a2a_2, \ldots, ana_n (0aii0 \le a_i \le i) — the elements of the array aa. It's guaranteed that aiai+1a_i \le a_{i+1} for 1i<n1\le i < n.

If there's no such array, print a single line containing 1-1.

Otherwise, print a single line containing nn integers b1b_1, b2b_2, \ldots, bnb_n (0bi1060 \le b_i \le 10^6)

If there are multiple answers, print any.

Input

The first line contains an integer nn (1n1051 \le n \le 10^5) — the length of the array aa.

The second line contains nn integers a1a_1, a2a_2, \ldots, ana_n (0aii0 \le a_i \le i) — the elements of the array aa. It's guaranteed that aiai+1a_i \le a_{i+1} for 1i<n1\le i < n.

Output

If there's no such array, print a single line containing 1-1.

Otherwise, print a single line containing nn integers b1b_1, b2b_2, \ldots, bnb_n (0bi1060 \le b_i \le 10^6)

If there are multiple answers, print any.

Samples

输入数据 1

3
1 2 3

输出数据 1

0 1 2

输入数据 2

4
0 0 0 2

输出数据 2

1 3 4 0

输入数据 3

3
1 1 3

输出数据 3

0 2 1

Note

In the second test case, other answers like [1,1,1,0][1,1,1,0], for example, are valid.