Different Adjacent

Limits: 2 sec., 512 MiB

You are given a sequence $a$ of $n$ integers.

Construct a sequence $b$ of $n$ integers satisfying the following conditions.

• $b_i \ge a_i$ for all $1 \le i \le n$.

• Adjacent elements of $b$ are distinct.

• $\max_{1 \le i \le n} (b_i - a_i)$ is minimum possible.

Input

The first line contains an integer $n$ – the number of elements in sequence $a$.

The second line contains $n$ integers $a_i$ – the elements of sequence $a$.

Output

Print $n$ integers $b_i$ – elements of sequence $b$.

Constraints

$1 \le n \le 2 \cdot 10^5$,

$1 \le a_i \le 10^9$.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 7 4 7	4 7 4 7

Input (stdin) сopy	Output (stdout) сopy
7 4 4 4 4 4 4 4	5 4 5 4 5 4 5

Notes

In the first example, it is possible to make $b = a$. In this case, $\max_{1 \le i \le n} (b_i - a_i) = 0$.

In the second example, $\max_{1 \le i \le n} (b_i - a_i) = 1$.