A. Simulation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While creating large language models, a group of researchers decided to conduct a partial simulation of the processes occurring during machine learning. They divided this task into many parts, and one of them has been assigned to you.

You are given an array $$$a$$$ of length $$$n$$$. You need to calculate an array $$$b$$$ of length $$$n$$$ such that $$$b_i = a_i$$$ if for any $$$j \lt i$$$ it holds that $$$a_j \ne a_i$$$, and $$$b_i = a_i + 1$$$ otherwise.

Input

The first line of input contains the number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (1\le a_i \le 10^9)$$$ — the values of the elements of array $$$a$$$.

Output

In a single line, output the array $$$b_1, b_2, \ldots, b_n$$$ – the answer to the problem.

Examples
Input
4
1 1 2 1
Output
1 2 2 2
Input
5
1 4 2 3 1
Output
1 4 2 3 2