Different Adjacent

Обмеження: 2 сек., 512 МіБ

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.

Вхідні дані

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

Вихідні дані

Print \(n\) integers \(b_i\) – elements of sequence \(b\).

Обмеження

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le a_i \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 4 7 4 7	4 7 4 7

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 4 4 4 4 4 4	5 4 5 4 5 4 5

Примітки

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