Description

Given an array $A=[A_1,A_2, \cdots A_N]$ of length $N$, the array may contain repeated integers.

Now Xiaoming wants to modify it into an array with no repeated integers using the following method. Xiaoming will modify $A_2,A_3, \cdots ,A_N$ in order.

When modifying $A_i$, Xiaoming checks whether $A_i$ has appeared in $A_1$ to $A_{i-1}$. If it has, Xiaoming adds $1$ to $A_i$. If the new $A_i$ still appears before, Xiaoming keeps adding $1$ to $A_i$ until $A_i$ does not appear in $A_1$ to $A_{i-1}$.

After $A_N$ is also modified as above, it is clear that there will be no duplicate integers in array $A$.

Given the initial array $A$, please compute the final array $A$.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1,A_2, \cdots ,A_N$.

Output Format

Output $N$ integers, in order: the final $A_1,A_2, \cdots ,A_N$.

5
2 1 1 3 4

2 1 3 4 5

Hint

For $80\%$ of the test cases, $1 \le N \le 10000$.

For all test cases, $1 \le N \le 10^5$, $1 \le A_i \le 10^6$.

Lanqiao Cup 2019 Provincial Contest A Group Problem H.

Translated by ChatGPT 5