Решение задачи Соседние замены с Codeforces

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

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

Заменить все вхождения 1 в массиве a на 2;
Заменить все вхождения 2 в массиве a на 1;
Заменить все вхождения 3 в массиве a на 4;
Заменить все вхождения 4 в массиве a на 3;
Заменить все вхождения 5 в массиве a на 6;
Заменить все вхождения 6 в массиве a на 5;
…
Заменить все вхождения 109−1 в массиве a на 109;
Заменить все вхождения 109 в массиве a на 109−1.
Заметим, что многоточие в середине алгоритма означает, что Мишка применяет эти замены к каждой паре соседних чисел (2i−1,2i) для всех i∈{1,2,…,5⋅108}, как это описано выше.

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

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

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