CF1738D Permutation Addicts

给定一个由 $1$ 到 $n$ 的整数构成的排列 $a_1, a_2, \dots, a_n$，以及一个阈值 $k$，其中 $0 \leq k \leq n$，你需要按如下方式计算序列 $b_1, b_2, \dots, b_n$。 对于每个 $1 \leq i \leq n$，按递增顺序，令 $x = a_i$。 - 如果 $x \leq k$，则将 $b_{x}$ 设为最后一个满足 $a_j > k$ 的 $a_j$（$1 \leq j < i$）。如果不存在这样的 $a_j$，则令 $b_{x} = n+1$。 - 如果 $x > k$，则将 $b_{x}$ 设为最后一个满足 $a_j \leq k$ 的 $a_j$（$1 \leq j < i$）。如果不存在这样的 $a_j$，则令 $b_{x} = 0$。 不幸的是，在序列 $b_1, b_2, \dots, b_n$ 完全计算出来后，排列 $a_1, a_2, \dots, a_n$ 和阈值 $k$ 都被丢弃了。 现在你只拥有序列 $b_1, b_2, \dots, b_n$。你的任务是找出任意一组可能的排列 $a_1, a_2, \dots, a_n$ 和阈值 $k$，使得它们能够生成给定的序列 $b_1, b_2, \dots, b_n$。保证至少存在一组排列 $a_1, a_2, \dots, a_n$ 和阈值 $k$ 能够生成该序列。 一个长度为 $n$ 的排列是指包含 $1$ 到 $n$ 的所有整数且每个整数恰好出现一次的序列。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的组数。接下来的每组测试用例描述如下。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示排列 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \leq b_i \leq n+1$），表示序列 $b$ 的元素。 保证至少存在一组排列 $a_1, a_2, \dots, a_n$ 和阈值 $k$ 能够生成该序列 $b_1, b_2, \dots, b_n$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，第一行输出阈值 $k$（$0 \leq k \leq n$），第二行输出排列 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$），使得该排列和阈值 $k$ 能够生成给定的序列 $b_1, b_2, \dots, b_n$。如果有多组解，你可以输出任意一组。

对于第一个测试用例，排列 $a = [1,3,2,4]$ 和阈值 $k = 2$ 会生成如下序列 $b$： - 当 $i = 1$ 时，$x = a_i = 1 \leq k$，不存在 $a_j > k$，因此 $b_1 = n + 1 = 5$。 - 当 $i = 2$ 时，$x = a_i = 3 > k$，最后一个 $a_j \leq k$ 是 $a_1$，因此 $b_3 = a_1 = 1$。 - 当 $i = 3$ 时，$x = a_i = 2 \leq k$，最后一个 $a_j > k$ 是 $a_2$，因此 $b_2 = a_2 = 3$。 - 当 $i = 4$ 时，$x = a_i = 4 > k$，最后一个 $a_j \leq k$ 是 $a_3$，因此 $b_4 = a_3 = 2$。 最终得到序列 $b = [5,3,1,2]$。对于第二个测试用例，排列 $a = [1,2,3,4,5,6]$ 和阈值 $k = 3$ 会生成如下序列 $b$： - 当 $i = 1, 2, 3$ 时，$a_i \leq k$，不存在 $a_j > k$，因此 $b_1 = b_2 = b_3 = n + 1 = 7$。 - 当 $i = 4, 5, 6$ 时，$a_i > k$，最后一个 $a_j \leq k$ 是 $a_3$，因此 $b_4 = b_5 = b_6 = a_3 = 3$。 最终得到序列 $b = [7,7,7,3,3,3]$。对于第三个测试用例，排列 $a = [6,5,4,3,2,1]$ 和阈值 $k = 3$ 会生成如下序列 $b$： - 当 $i = 1, 2, 3$ 时，$a_i > k$，不存在 $a_j \leq k$，因此 $b_4 = b_5 = b_6 = 0$。 - 当 $i = 4, 5, 6$ 时，$a_i \leq k$，最后一个 $a_j > k$ 是 $a_3$，因此 $b_1 = b_2 = b_3 = a_3 = 4$。 最终得到序列 $b = [4,4,4,0,0,0]$。 由 ChatGPT 4.1 翻译