题目描述

Mishka 收到了一个长度为 $n$ 的整数数组 $a$ 作为生日礼物（真是个惊喜）。

Mishka 并不喜欢这个礼物，想要对它做些改变。他发明了一种算法，称之为“Mishka 的相邻替换算法”。该算法的步骤如下：

• 将数组 $a$ 中每个 $1$ 替换为 $2$；
• 将数组 $a$ 中每个 $2$ 替换为 $1$；
• 将数组 $a$ 中每个 $3$ 替换为 $4$；
• 将数组 $a$ 中每个 $4$ 替换为 $3$；
• 将数组 $a$ 中每个 $5$ 替换为 $6$；
• 将数组 $a$ 中每个 $6$ 替换为 $5$；
• $\dots$
• 将数组 $a$ 中每个 $10^9 - 1$ 替换为 $10^9$；
• 将数组 $a$ 中每个 $10^9$ 替换为 $10^9 - 1$。

注意，中间的省略号表示 Mishka 对每一对相邻整数（即每个 $i \in \{1, 2, \ldots, 5 \cdot 10^8\}$，对应的 $(2i-1, 2i)$）都按照上述方式进行替换。

例如，对于数组 $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]$。后续的步骤不会再改变数组。

Mishka 很懒，不想亲自执行这些操作，但他很想知道最终的结果。请你帮他计算出最终的数组。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 1000$），表示 Mishka 生日礼物的元素个数（令人惊讶的是，是一个数组）。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组中的元素。

输出格式

输出 $n$ 个整数 $b_1, b_2, \dots, b_n$，其中 $b_i$ 表示对数组 $a$ 应用“Mishka 的相邻替换算法”后，第 $i$ 个元素的最终值。注意，数组元素的顺序不能改变。

说明/提示

第一个样例在题目描述中已经给出。

由 ChatGPT 4.1 翻译

样例

5
1 2 4 5 10

1 1 3 5 9

10
10000 10 50605065 1 5 89 5 999999999 60506056 1000000000

9999 9 50605065 1 5 89 5 999999999 60506055 999999999