题目描述

给定一个长度为 $n$ 的整数数组 $a$。你可以进行如下操作零次或多次：

• 每次操作选择一个下标 $i$（$1 \le i \le n$），将 $a_i$ 加 $1$，然后把 $a_i$ 移动到数组的末尾（最右侧）。例如，如果 $a = [3, 5, 1, 9]$，你选择 $i = 2$，则数组变为 $[3, 1, 9, 6]$。

请你通过若干次操作，使得最终得到的数组字典序最小。

$^*$ 数组 $c$ 的字典序小于数组 $d$ 当且仅当满足以下条件之一：

• $c$ 是 $d$ 的前缀，且 $c \ne d$；
• 在第一个不同的位置，$c$ 的元素小于 $d$ 的对应元素。

输入格式

每组测试数据包含多组测试用例。第一行包含测试用例个数 $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$。

输出格式

对于每组测试用例，输出通过若干次操作后能得到的字典序最小的数组。

说明/提示

由 ChatGPT 4.1 翻译

样例

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

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