← 返回题目列表

Codeforces · 1852/E

E. 竞争

中文机器翻译题面 查看原题

Ntarsis 有一个长度为 $$$n$$$ 的数组 $$$a$$$。

子数组 $$$a_l \dots a_r$$$ ($$$1 \leq l \leq r \leq n$$$) 的幂定义为:

- 最大值 $$$x$$$ 使得 $$$a_l \dots a_r$$$ 包含 $$$x$$$ 并且 $$$a_1 \dots a_{l-1}$$$ 和 $$$a_{r+1} \dots a_n$$$ 都不包含 $$$x$$$。
- 如果不存在这样的$$$x$$$,则功率为$$$0$$$。

如果满足以下条件,则将数组 $$$b$$$ 称为 $$$a$$$ 的竞争对手:

- $$$a$$$ 和 $$$b$$$ 的长度都等于某个 $$$n$$$。
- 在所有 $$$l, r$$$ 中,其中 $$$1 \leq l \leq r \leq n$$$,$$$a_l \dots a_r$$$ 的幂等于 $$$b_l \dots b_r$$$ 的幂。
- $$$b$$$ 的元素为正。

Ntarsis 希望你找到 $$$a$$$ 的竞争对手 $$$b$$$,使得 $$$b_i$$$ 超过 $$$1 \leq i \leq n$$$ 的总和最大化。帮助他完成这个任务!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 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$$$ - $$$a$$$ 的有效竞争对手,使得 $$$b_1 + b_2 + \cdots + b_n$$$ 最大。

如果存在多个总和最大的对手,则输出其中任何一个。

示例

输入 #1

7
5
1 4 1 3 3
5
1 4 1 8 8
5
2 1 1 1 2
8
3 2 3 5 2 2 5 3
8
1 1 1 1 4 3 3 3
10
1 9 5 9 8 1 5 8 9 1
16
1 1 1 1 5 5 5 5 9 9 9 9 7 7 7 7

输出 #1

2 4 2 3 3
3 4 3 8 8
2 1 2 1 2
4 2 4 5 5 2 5 4
1 2 2 1 4 3 2 3
7 9 5 9 8 9 5 8 9 7
1 8 8 1 5 8 8 5 9 9 9 9 7 8 8 7

注意

对于第一个测试用例,最大和的竞争对手是 $$$[2, 4, 2, 3, 3]$$$。

$$$[2, 4, 2, 3, 3]$$$ 可以被证明是 $$$[1, 4, 1, 3, 3]$$$ 的竞争对手。

$$$a$$$ 和 $$$b$$$ 的所有可能子数组及其相应的幂如下:

- $$$a[1:1] = [1] = 0$$$ 的幂,$$$b[1:1] = [2] = 0$$$ 的幂。
- $$$a[1:2] = [1, 4] = 4$$$ 的幂,$$$b[1:2] = [2, 4] = 4$$$ 的幂。
- $$$a[1:3] = [1, 4, 1] = 4$$$ 的幂,$$$b[1:3] = [2, 4, 2] = 4$$$ 的幂。
- $$$a[1:4] 的幂 = [1, 4, 1, 3] = 4$$$,$$$b[1:4] 的幂 = [2, 4, 2, 3] = 4$$$。
- $$$a[1:5] 的幂 = [1, 4, 1, 3, 3] = 4$$$,$$$b[1:5] 的幂 = [2, 4, 2, 3, 3] = 4$$$。
- $$$a[2:2] = [4] = 4$$$ 的幂,$$$b[2:2] = [4] = 4$$$ 的幂。
- $$$a[2:3] = [4, 1] = 4$$$ 的幂,$$$b[2:3] = [4, 2] = 4$$$ 的幂。
- $$$a[2:4] = [4, 1, 3] = 4$$$ 的幂,$$$b[2:4] = [4, 2, 3] = 4$$$ 的幂。
- $$$a[2:5] = [4, 1, 3, 3] = 4$$$ 的幂,$$$b[2:5] = [4, 2, 3, 3] = 4$$$ 的幂。
- $$$a[3:3] = [1] = 0$$$ 的幂,$$$b[3:3] = [2] = 0$$$ 的幂。
- $$$a[3:4] = [1, 3] = 0$$$ 的幂,$$$b[3:4] = [2, 3] = 0$$$ 的幂。
- $$$a[3:5] = [1, 3, 3] = 3$$$ 的幂,$$$b[3:5] = [2, 3, 3] = 3$$$ 的幂。
- $$$a[4:4] = [3] = 0$$$ 的幂,$$$b[4:4] = [3] = 0$$$ 的幂。
- $$$a[4:5] = [3, 3] = 3$$$ 的幂,$$$b[4:5] = [3, 3] = 3$$$ 的幂。
- $$$a[5:5] = [3] = 0$$$ 的幂,$$$b[5:5] = [3] = 0$$$ 的幂。

可以证明不存在总和大于 $$$2 + 4 + 2 + 3 + 3 = 14$$$ 的竞争对手。