CF959D Mahmoud and Ehab and another array construction task

Mahmoud 有一个包含 $n$ 个整数的数组 $a$。他让 Ehab 找出另一个长度相同的数组 $b$，使得： - $b$ 字典序大于等于 $a$。 - $b_i \geq 2$。 - $b$ 是两两互质的：对于每个 $1 \leq i < j \leq n$，$b_i$ 和 $b_j$ 互质，即 $GCD(b_i, b_j) = 1$，其中 $GCD(w, z)$ 表示 $w$ 和 $z$ 的最大公约数。 Ehab 想选择一个特殊的数组，所以他希望在所有满足条件的数组中，字典序最小的那个。你能帮他找到吗？ 如果存在某个下标 $i$，使得 $x_i > y_i$，且对于所有 $1 \leq j < i$，$x_j = y_j$，则数组 $x$ 字典序大于数组 $y$。如果对于所有 $1 \leq i \leq n$，$x_i = y_i$，则数组 $x$ 等于数组 $y$。

第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示 $a$ 和 $b$ 的元素个数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(2 \leq a_i \leq 10^5)$，表示数组 $a$ 的元素。

输出 $n$ 个用空格分隔的整数，第 $i$ 个整数表示 $b_i$。

注意，在第二个样例中，数组已经是两两互质的，所以直接输出即可。 由 ChatGPT 4.1 翻译