CF1852E Rivalries

Ntarsis 有一个长度为 $n$ 的数组 $a$。 对于子数组 $a_l \dots a_r$（$1 \leq l \leq r \leq n$），其“power”定义如下： - 最大的值 $x$，满足 $a_l \dots a_r$ 包含 $x$，且 $a_1 \dots a_{l-1}$ 和 $a_{r+1} \dots a_n$ 都不包含 $x$。 - 如果不存在这样的 $x$，则 power 为 $0$。 如果数组 $b$ 满足以下条件，则称其为 $a$ 的“rival”： - $a$ 和 $b$ 的长度均为 $n$。 - 对所有 $1 \leq l \leq r \leq n$，$a_l \dots a_r$ 的 power 等于 $b_l \dots b_r$ 的 power。 - $b$ 的所有元素均为正整数。 Ntarsis 希望你找到一个 $a$ 的 rival 数组 $b$，使得 $b_i$ 的和（$1 \leq i \leq n$）最大。请帮助他完成这个任务！

每个测试点包含多个测试用例。第一行包含测试用例个数 $t$（$1 \le t \leq 10^5$）。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数 $b_1, b_2, \ldots, b_n$，表示一个合法的 rival 数组，并且 $b_1 + b_2 + \cdots + b_n$ 最大。 如果有多个最大和的 rival，输出其中任意一个即可。

对于第一个测试用例，一个最大和的 rival 是 $[2, 4, 2, 3, 3]$。 $[2, 4, 2, 3, 3]$ 可以证明是 $[1, 4, 1, 3, 3]$ 的 rival。 $a$ 和 $b$ 所有可能的子数组及其对应的 power 如下： - $a[1:1] = [1]$ 的 power 为 $0$，$b[1:1] = [2]$ 的 power 也为 $0$。 - $a[1:2] = [1, 4]$ 的 power 为 $4$，$b[1:2] = [2, 4]$ 的 power 也为 $4$。 - $a[1:3] = [1, 4, 1]$ 的 power 为 $4$，$b[1:3] = [2, 4, 2]$ 的 power 也为 $4$。 - $a[1:4] = [1, 4, 1, 3]$ 的 power 为 $4$，$b[1:4] = [2, 4, 2, 3]$ 的 power 也为 $4$。 - $a[1:5] = [1, 4, 1, 3, 3]$ 的 power 为 $4$，$b[1:5] = [2, 4, 2, 3, 3]$ 的 power 也为 $4$。 - $a[2:2] = [4]$ 的 power 为 $4$，$b[2:2] = [4]$ 的 power 也为 $4$。 - $a[2:3] = [4, 1]$ 的 power 为 $4$，$b[2:3] = [4, 2]$ 的 power 也为 $4$。 - $a[2:4] = [4, 1, 3]$ 的 power 为 $4$，$b[2:4] = [4, 2, 3]$ 的 power 也为 $4$。 - $a[2:5] = [4, 1, 3, 3]$ 的 power 为 $4$，$b[2:5] = [4, 2, 3, 3]$ 的 power 也为 $4$。 - $a[3:3] = [1]$ 的 power 为 $0$，$b[3:3] = [2]$ 的 power 也为 $0$。 - $a[3:4] = [1, 3]$ 的 power 为 $0$，$b[3:4] = [2, 3]$ 的 power 也为 $0$。 - $a[3:5] = [1, 3, 3]$ 的 power 为 $3$，$b[3:5] = [2, 3, 3]$ 的 power 也为 $3$。 - $a[4:4] = [3]$ 的 power 为 $0$，$b[4:4] = [3]$ 的 power 也为 $0$。 - $a[4:5] = [3, 3]$ 的 power 为 $3$，$b[4:5] = [3, 3]$ 的 power 也为 $3$。 - $a[5:5] = [3]$ 的 power 为 $0$，$b[5:5] = [3]$ 的 power 也为 $0$。 可以证明不存在比 $2 + 4 + 2 + 3 + 3 = 14$ 更大的 rival。 由 ChatGPT 4.1 翻译