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\).