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] $ .

题意翻译

有一个 $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$。