CF1506E Restoring the Permutation

一个排列是一个长度为 $n$ 的整数序列，包含从 $1$ 到 $n$ 的所有数字，且每个数字恰好出现一次。例如，$[1]$、$[3, 5, 2, 1, 4]$、$[1, 3, 2]$ 都是排列，而 $[2, 3, 2]$、$[4, 3, 1]$、$[0]$ 不是排列。 Polycarp 得到一个 $1$ 到 $n$ 的排列 $p$。然而，当 Polycarp 回家时，他发现口袋里的排列 $p$ 变成了数组 $q$，变化规则如下： - $q_i = \max(p_1, p_2, \ldots, p_i)$。 现在 Polycarp 想知道，可能被呈现给他的排列中，字典序最小和字典序最大的分别是什么。 长度为 $n$ 的数组 $a$ 如果存在某个下标 $i$（$1 \le i \le n$），使得数组 $a$ 和 $b$ 的前 $i-1$ 个元素都相同，且 $a$ 的第 $i$ 个元素小于 $b$ 的第 $i$ 个元素，则称 $a$ 的字典序小于 $b$。例如，$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 \times 10^5$）。 第二行包含 $n$ 个整数 $q_1, q_2, \ldots, q_n$（$1 \le q_i \le n$）。 保证数组 $q$ 是通过题目描述中的规则由某个排列 $p$ 得到的。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出两行： - 第一行输出 $n$ 个整数，表示可能被最初呈现给 Polycarp 的字典序最小的排列； - 第二行输出 $n$ 个整数，表示可能被最初呈现给 Polycarp 的字典序最大的排列。

由 ChatGPT 4.1 翻译