Permutation Addicts

题意翻译

有一个 $n$ 个数的排列 $a$ 和一个数 $k (0 \le k \le n)$，你计算出了一个有 $n$ 个数的序列 $b$，计算方法如下： - 当 $a_i \le k$ 时，若存在 $a_j > k (1 \le j < i)$ 且 $i - j$ 最小，则 $b_{a_i} = a_j$，否则 $b_{a_i} = n + 1$； - 当 $a_i > k$ 时，若存在 $a_j \le k (1 \le j < i)$ 且 $i - j$ 最小，则 $b_{a_i} = a_j$，否则 $b_{a_i} = 0$。 目前你知道 $b$ 与 $n$，请求出任意一种 $a$ 及对应的 $k$。

题目描述

Given a permutation $ a_1, a_2, \dots, a_n $ of integers from $ 1 $ to $ n $ , and a threshold $ k $ with $ 0 \leq k \leq n $ , you compute a sequence $ b_1, b_2, \dots, b_n $ as follows. For every $ 1 \leq i \leq n $ in increasing order, let $ x = a_i $ . - If $ x \leq k $ , set $ b_{x} $ to the last element $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j > k $ . If no such element $ a_j $ exists, set $ b_{x} = n+1 $ . - If $ x > k $ , set $ b_{x} $ to the last element $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j \leq k $ . If no such element $ a_j $ exists, set $ b_{x} = 0 $ . Unfortunately, after the sequence $ b_1, b_2, \dots, b_n $ has been completely computed, the permutation $ a_1, a_2, \dots, a_n $ and the threshold $ k $ are discarded. Now you only have the sequence $ b_1, b_2, \dots, b_n $ . Your task is to find any possible permutation $ a_1, a_2, \dots, a_n $ and threshold $ k $ that produce the sequence $ b_1, b_2, \dots, b_n $ . It is guaranteed that there exists at least one pair of permutation $ a_1, a_2, \dots, a_n $ and threshold $ k $ that produce the sequence $ b_1, b_2, \dots, b_n $ . A permutation of integers from $ 1 $ to $ n $ is a sequence of length $ n $ which contains all integers from $ 1 $ to $ n $ exactly once.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 10^5 $ ), indicating the length of the permutation $ a $ . The second line of each test case contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 0 \leq b_i \leq n+1 $ ), indicating the elements of the sequence $ b $ . It is guaranteed that there exists at least one pair of permutation $ a_1, a_2, \dots, a_n $ and threshold $ k $ that produce the sequence $ b_1, b_2, \dots, b_n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output the threshold $ k $ ( $ 0 \leq k \leq n $ ) in the first line, and then output the permutation $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq n $ ) in the second line such that the permutation $ a_1, a_2, \dots, a_n $ and threshold $ k $ produce the sequence $ b_1, b_2, \dots, b_n $ . If there are multiple solutions, you can output any of them.

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

For the first test case, permutation $ a = [1,3,2,4] $ and threshold $ k = 2 $ will produce sequence $ b $ as follows. - When $ i = 1 $ , $ x = a_i = 1 \leq k $ , there is no $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j > k $ . Therefore, $ b_1 = n + 1 = 5 $ . - When $ i = 2 $ , $ x = a_i = 3 > k $ , the last element $ a_j $ that $ a_j \leq k $ is $ a_1 $ . Therefore, $ b_3 = a_1 = 1 $ . - When $ i = 3 $ , $ x = a_i = 2 \leq k $ , the last element $ a_j $ that $ a_j > k $ is $ a_2 $ . Therefore, $ b_2 = a_2 = 3 $ . - When $ i = 4 $ , $ x = a_i = 4 > k $ , the last element $ a_j $ that $ a_j \leq k $ is $ a_3 $ . Therefore, $ b_4 = a_3 = 2 $ . Finally, we obtain sequence $ b = [5,3,1,2] $ . For the second test case, permutation $ a = [1,2,3,4,5,6] $ and threshold $ k = 3 $ will produce sequence $ b $ as follows. - When $ i = 1, 2, 3 $ , $ a_i \leq k $ , there is no $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j > k $ . Therefore, $ b_1 = b_2 = b_3 = n + 1 = 7 $ . - When $ i = 4, 5, 6 $ , $ a_i > k $ , the last element $ a_j $ that $ a_j \leq k $ is $ a_3 $ . Therefore, $ b_4 = b_5 = b_6 = a_3 = 3 $ . Finally, we obtain sequence $ b = [7,7,7,3,3,3] $ . For the third test case, permutation $ a = [6,5,4,3,2,1] $ and threshold $ k = 3 $ will produce sequence $ b $ as follows. - When $ i = 1, 2, 3 $ , $ a_i > k $ , there is no $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j \leq k $ . Therefore, $ b_4 = b_5 = b_6 = 0 $ . - When $ i = 4, 5, 6 $ , $ a_i \leq k $ , the last element $ a_j $ that $ a_j > k $ is $ a_3 $ . Therefore, $ b_1 = b_2 = b_3 = a_3 = 4 $ . Finally, we obtain sequence $ b = [4,4,4,0,0,0] $ .

**题意翻译**

给定一个从1到n的整数排列a_1, a_2, ..., a_n，以及一个阈值k（0 ≤ k ≤ n），你计算出一个序列b_1, b_2, ..., b_n的计算方法如下：

对于每个1 ≤ i ≤ n，按递增顺序，设x = a_i。

- 如果x ≤ k，则将b_x设置为最后一个a_j（1 ≤ j < i）使得a_j > k。如果没有这样的元素a_j存在，则设置b_x = n+1。
- 如果x > k，则将b_x设置为最后一个a_j（1 ≤ j < i）使得a_j ≤ k。如果没有这样的元素a_j存在，则设置b_x = 0。

不幸的是，在序列b_1, b_2, ..., b_n完全计算出来后，排列a_1, a_2, ..., a_n和阈值k都被丢弃了。

现在你只有序列b_1, b_2, ..., b_n。你的任务是找到任何可能的排列a_1, a_2, ..., a_n和阈值k，它们能够产生序列b_1, b_2, ..., b_n。保证至少存在一对排列a_1, a_2, ..., a_n和阈值k，能够产生序列b_1, b_2, ..., b_n。

从1到n的整数排列是长度为n的序列，它恰好包含一次从1到n的所有整数。

**输入输出格式**

**输入格式**

每个测试用例包含多个测试案例。第一行包含一个整数t（1 ≤ t ≤ 10^5）——测试案例的数量。接下来的行包含每个测试案例的描述。

每个测试案例的第一行包含一个整数n（1 ≤ n ≤ 10^5），表示排列a的长度。

每个测试案例的第二行包含n个整数b_1, b_2, ..., b_n（0 ≤ b_i ≤ n+1），表示序列b的元素。

保证至少存在一对排列a_1, a_2, ..., a_n和阈值k，能够产生序列b_1, b_2, ..., b_n。

保证所有测试案例的n之和不超过10^5。

**输出格式**

对于每个测试案例，第一行输出阈值k（0 ≤ k ≤ n），然后在第二行输出排列a_1, a_2, ..., a_n（1 ≤ a_i ≤ n），使得排列a_1, a_2, ..., a_n和阈值k能够产生序列b_1, b_2, ..., b_n。如果存在多个解决方案，你可以输出其中任何一个。**题意翻译** 给定一个从1到n的整数排列a_1, a_2, ..., a_n，以及一个阈值k（0 ≤ k ≤ n），你计算出一个序列b_1, b_2, ..., b_n的计算方法如下： 对于每个1 ≤ i ≤ n，按递增顺序，设x = a_i。 - 如果x ≤ k，则将b_x设置为最后一个a_j（1 ≤ j < i）使得a_j > k。如果没有这样的元素a_j存在，则设置b_x = n+1。 - 如果x > k，则将b_x设置为最后一个a_j（1 ≤ j < i）使得a_j ≤ k。如果没有这样的元素a_j存在，则设置b_x = 0。 不幸的是，在序列b_1, b_2, ..., b_n完全计算出来后，排列a_1, a_2, ..., a_n和阈值k都被丢弃了。 现在你只有序列b_1, b_2, ..., b_n。你的任务是找到任何可能的排列a_1, a_2, ..., a_n和阈值k，它们能够产生序列b_1, b_2, ..., b_n。保证至少存在一对排列a_1, a_2, ..., a_n和阈值k，能够产生序列b_1, b_2, ..., b_n。 从1到n的整数排列是长度为n的序列，它恰好包含一次从1到n的所有整数。 **输入输出格式** **输入格式** 每个测试用例包含多个测试案例。第一行包含一个整数t（1 ≤ t ≤ 10^5）——测试案例的数量。接下来的行包含每个测试案例的描述。 每个测试案例的第一行包含一个整数n（1 ≤ n ≤ 10^5），表示排列a的长度。 每个测试案例的第二行包含n个整数b_1, b_2, ..., b_n（0 ≤ b_i ≤ n+1），表示序列b的元素。 保证至少存在一对排列a_1, a_2, ..., a_n和阈值k，能够产生序列b_1, b_2, ..., b_n。 保证所有测试案例的n之和不超过10^5。 **输出格式** 对于每个测试案例，第一行输出阈值k（0 ≤ k ≤ n），然后在第二行输出排列a_1, a_2, ..., a_n（1 ≤ a_i ≤ n），使得排列a_1, a_2, ..., a_n和阈值k能够产生序列b_1, b_2, ..., b_n。如果存在多个解决方案，你可以输出其中任何一个。