排列是从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 整数序列,其中所有数字恰好出现一次。例如,$$$[1]$$$、$$$[3, 5, 2, 1, 4]$$$、$$$[1, 3, 2]$$$ 是排列,$$$[2, 3, 2]$$$、$$$[4, 3, 1]$$$、$$$[0]$$$ 不是排列。
Polycarp 被呈现了从 $$$1$$$ 到 $$$n$$$ 的数字排列 $$$p$$$。然而,当波利卡普回到家时,他注意到在他的口袋里,排列$$$p$$$已经根据以下规则变成了数组$$$q$$$:
- $$$q_i = \max(p_1, p_2, \ldots, p_i)$$$。
现在波利卡普想知道可以向他呈现哪些词典编目最小和词典编目最大排列。
如果存在索引 $$$i$$$ ($$$1 \le i \le n$$$),使得数组 $$$a$$$ 和 $$$b$$$ 的第一个 $$$i-1$$$ 元素是相同,并且数组 $$$a$$$ 的第 $$$i$$$ 元素小于数组 $$$b$$$ 的第 $$$i$$$ 个元素。例如,数组 $$$a=[1, 3, 2, 3]$$$ 按字典顺序小于数组 $$$b=[1, 3, 4, 2]$$$。
例如,如果 $$$n=7$$$ 且 $$$p=[3, 2, 4, 1, 7, 5, 6]$$$,则 $$$q=[3, 3, 4, 4, 7, 7, 7]$$$ 并且以下排列最初可能为 $$$p$$$:
- $$$[3, 1, 4, 2, 7, 5, 6]$$$(字典顺序最小排列);
- $$$[3, 1, 4, 2, 7, 6, 5]$$$;
- $$$[3, 2, 4, 1, 7, 5, 6]$$$;
- $$$[3, 2, 4, 1, 7, 6, 5]$$$(按字典顺序排列的最大排列)。
对于给定的数组 $$$q$$$,找到最初可以提交给 Polycarp 的字典顺序最小和字典顺序最大排列。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$)。
保证数组 $$$q$$$ 是通过将语句中的规则应用于某些排列 $$$p$$$ 来获得的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两行:
- 在第一行输出 $$$n$$$ 整数 - 按字典顺序排列的最小排列,最初可以呈现给波利卡普;
- 在第二行打印 $$$n$$$ 整数 - 按字典顺序排列的最大排列,最初可以呈现给波利卡普;
示例
输入 #1
4 7 3 3 4 4 7 7 7 4 1 2 3 4 7 3 4 5 5 5 7 7 1 1
输出 #1
3 1 4 2 7 5 6 3 2 4 1 7 6 5 1 2 3 4 1 2 3 4 3 4 5 1 2 7 6 3 4 5 2 1 7 6 1 1