Вам задано послідовність з цілих чисел.
Побудуйте послідовність з цілих чисел, що задовольняє такі умови.
b_i \ge a_i для всіх 1 \le i \le n.
Сусідні елементи різні.
\max_{1 \le i \le n} (b_i - a_i) є мінімально можливим.
У першому рядку задано ціле число – кількість елементів у послідовності .
У другому рядку задано цілих чисел a_i – елементи послідовності .
1 \le n \le 2 \cdot 10^5,
1 \le a_i \le 10^9.
Виведіть цілих чисел b_i – елементи послідовності .
Example
Example 1
У першому прикладі можна зробити b = a. У цьому випадку \max_{1 \le i \le n} (b_i - a_i) = 0.
У другому прикладі \max_{1 \le i \le n} (b_i - a_i) = 1.