Різні сусідні

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

Вам задано послідовність \(a\) з \(n\) цілих чисел.

Побудуйте послідовність \(b\) з \(n\) цілих чисел, що задовольняє такі умови.

• \(b_i \ge a_i\) для всіх \(1 \le i \le n\).

• Сусідні елементи \(b\) різні.

• \(\max_{1 \le i \le n} (b_i - a_i)\) є мінімально можливим.

Вхідні дані

У першому рядку задано ціле число \(n\) – кількість елементів у послідовності \(a\).

У другому рядку задано \(n\) цілих чисел \(a_i\) – елементи послідовності \(a\).

Вихідні дані

Виведіть \(n\) цілих чисел \(b_i\) – елементи послідовності \(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

Примітки

У першому прикладі можна зробити \(b = a\). У цьому випадку \(\max_{1 \le i \le n} (b_i - a_i) = 0\).

У другому прикладі \(\max_{1 \le i \le n} (b_i - a_i) = 1\).