В подарок на день рождения Мишка получил массив целых чисел $$$a$$$ длины $$$n$$$ (какая неожиданность!).

Мишке не нравится этот подарок и он хочет как-нибудь его изменить. Он изобрел алгоритм и назвал его «Алгоритм Мишки для Соседних Замен». Этот алгоритм может быть представлен в виде последовательности ходов:

• Заменить все вхождения $$$1$$$ в массиве $$$a$$$ на $$$2$$$;
• Заменить все вхождения $$$2$$$ в массиве $$$a$$$ на $$$1$$$;
• Заменить все вхождения $$$3$$$ в массиве $$$a$$$ на $$$4$$$;
• Заменить все вхождения $$$4$$$ в массиве $$$a$$$ на $$$3$$$;
• Заменить все вхождения $$$5$$$ в массиве $$$a$$$ на $$$6$$$;
• Заменить все вхождения $$$6$$$ в массиве $$$a$$$ на $$$5$$$;
• $$$\dots$$$
• Заменить все вхождения $$$10^9 - 1$$$ в массиве $$$a$$$ на $$$10^9$$$;
• Заменить все вхождения $$$10^9$$$ в массиве $$$a$$$ на $$$10^9 - 1$$$.

Заметим, что многоточие в середине алгоритма означает, что Мишка применяет эти замены к каждой паре соседних чисел ($$$2i - 1, 2i$$$) для всех $$$i \in\{1, 2, \ldots, 5 \cdot 10^8\}$$$, как это описано выше.

Например, для массива $$$a = [1, 2, 4, 5, 10]$$$ следующая последовательность массивов описывает алгоритм:

$$$[1, 2, 4, 5, 10]$$$ $$$\rightarrow$$$ (заменить все вхождения $$$1$$$ на $$$2$$$) $$$\rightarrow$$$ $$$[2, 2, 4, 5, 10]$$$ $$$\rightarrow$$$ (заменить все вхождения $$$2$$$ на $$$1$$$) $$$\rightarrow$$$ $$$[1, 1, 4, 5, 10]$$$ $$$\rightarrow$$$ (заменить все вхождения $$$3$$$ на $$$4$$$) $$$\rightarrow$$$ $$$[1, 1, 4, 5, 10]$$$ $$$\rightarrow$$$ (заменить все вхождения $$$4$$$ на $$$3$$$) $$$\rightarrow$$$ $$$[1, 1, 3, 5, 10]$$$ $$$\rightarrow$$$ (заменить все вхождения $$$5$$$ на $$$6$$$) $$$\rightarrow$$$ $$$[1, 1, 3, 6, 10]$$$ $$$\rightarrow$$$ (заменить все вхождения $$$6$$$ на $$$5$$$) $$$\rightarrow$$$ $$$[1, 1, 3, 5, 10]$$$ $$$\rightarrow$$$ $$$\dots$$$ $$$\rightarrow$$$ $$$[1, 1, 3, 5, 10]$$$ $$$\rightarrow$$$ (заменить все вхождения $$$10$$$ на $$$9$$$) $$$\rightarrow$$$ $$$[1, 1, 3, 5, 9]$$$. Дальнейшие шаги алгоритма не изменят массив.

Мишка очень ленивый и он не хочет сам применять эти изменения. Но ему очень интересно узнать, как будет выглядеть результат их применения. Помогите Мишке найти его.