← 返回题目列表

Codeforces · 1930/C

C. 字典顺序最大

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

堆栈有一个长度为 $$$n$$$ 的数组 $$$a$$$。他还有一个空集$$$S$$$。请注意,$$$S$$$ 不是多重集。

他将执行以下三步操作 $$$n$$$ 次:

1. 选择索引 $$$i$$$,使得 $$$1 \leq i \leq |a|$$$。
2. 将$$$^\dagger$$$ $$$a_i + i$$$ 插入$$$S$$$。
3. 从$$$a$$$ 中删除$$$a_i$$$。请注意,$$$a_i$$$ 右侧的所有元素的索引将减少 $$$1$$$。

请注意,在 $$$n$$$ 操作之后,$$$a$$$ 将为空。

Stack 现在将构造一个新数组 $$$b$$$,该数组按降序排列 $$$S$$$。形式上,$$$b$$$ 是一个大小为 $$$|S|$$$ 的数组,其中 $$$b_i$$$ 是所有 $$$1 \leq i \leq |S|$$$ 的 $$$S$$$ 的第 $$$i$$$ 个最大元素。

找到 Stack 可以生成的按字典顺序最大的$$$^\ddagger$$$ $$$b$$$。

$$$^\dagger$$$ 集合只能包含唯一元素。插入集合中已存在的元素不会更改集合的元素。

$$$^\ddagger$$$ 当且仅当满足以下条件之一时,数组 $$$p$$$ 按字典顺序大于序列 $$$q$$$:

- $$$q$$$ 是 $$$p$$$ 的前缀,但 $$$p \ne q$$$;或
- 在 $$$p$$$ 和 $$$q$$$ 不同的第一个位置,数组 $$$p$$$ 的元素比 $$$q$$$ 中的相应元素大。

请注意,$$$[3,1,4,1,5]$$$ 按字典顺序大于 $$$[3,1,3]$$$、$$$[\,]$$$ 和 $$$[3,1,4,1]$$$,但不大于 $$$[3,1,4,1,5,9]$$$, $$$[3,1,4,1,5]$$$和$$$[4]$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_{n}$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出字典顺序最大的$$$b$$$。

示例

输入 #1

3
2
2 1
5
1 100 1000 1000000 1000000000
3
6 4 8

输出 #1

3 2 
1000000005 1000004 1003 102 2 
11 7 6

注意

在第一个测试用例中,在第一个操作中选择$$$i=1$$$,在$$$S$$$中插入$$$a_1 + 1 = 3$$$,并从$$$a$$$中删除$$$a_1$$$。第一次操作后,$$$a$$$ 变为 $$$a=[1]$$$。在第二个操作中,我们再次选择$$$i=1$$$,并在$$$S$$$中插入$$$a_1 + 1 = 2$$$。因此$$$S=\{2, 3\}$$$,并且$$$b = [3, 2]$$$。

请注意,如果您在第一个操作中选择 $$$i=2$$$,并在第二个操作中选择 $$$i=1$$$,则 $$$S=\{3\}$$$ 作为 $$$3$$$ 将被插入两次,结果是 $$$b=[3]$$$。

由于 $$$[3,2]$$$ 按字典顺序大于 $$$[3]$$$,因此我们应该在第一个操作中选择 $$$i=1$$$。

在第二个测试用例中,在每个操作中选择最后一个元素。