В подарок на день рождения Мишка получил массив целых чисел \(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]\). Дальнейшие шаги алгоритма не изменят массив.
Мишка очень ленивый и он не хочет сам применять эти изменения. Но ему очень интересно узнать, как будет выглядеть результат их применения. Помогите Мишке найти его.