← 返回题目列表

Codeforces · 2046/B

B. 有代价地后退

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

给定一个整数数组 $$$a$$$,长度为 $$$n$$$。您可以执行以下操作零次或多次:

- 在一次操作中选择索引 $$$i$$$ ($$$1 \le i \le n$$$),分配 $$$a_i := a_i + 1$$$,然后将 $$$a_i$$$ 移动到数组的末尾(到最右边的位置)。例如,如果 $$$a = [3, 5, 1, 9]$$$,并且您选择 $$$i = 2$$$,则数组将变为 $$$[3, 1, 9, 6]$$$。

找到通过执行这些操作可以获得的按字典顺序最小的$$$^{\text{*}}$$$ 数组。

输入

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

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),即数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),即数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印您可以获得的按字典顺序排列的最小数组。

示例

输入 #1

3
3
2 1 3
5
1 2 2 1 4
6
1 2 3 6 5 4

输出 #1

1 3 3 
1 1 3 3 5 
1 2 3 4 6 7