CF2124I Lexicographic Partition

Given an array $ a $ , define $ f(a) $ as follows: - Let $ k $ be an integer with $ 1 \leq k \leq n $ . - Partition $ a $ into $ k $ subarrays $ ^{\text{∗}} $ $ s_1,s_2,\ldots,s_k $ such that $ s_1+s_2+\ldots+s_k=a $ . Here, $ + $ represents array concatenation. - Let $ b $ be an empty array. For each $ i $ from $ 1 $ to $ k $ in order, append the minimum element of $ s_i $ to the end of $ b $ . - Over all possible $ k $ and partitions, $ f(a) $ is the value of $ k $ such that there exists a partition that produces the lexicographically largest $ b $ $ ^{\text{†}} $ . You are given $ n $ integers $ x_1,x_2,\ldots,x_n $ . Please determine if there exists a permutation $ ^{\text{‡}} $ $ a $ such that $ f([a_1,a_2,\ldots,a_i])=x_i $ for each $ 1 \leq i \leq n $ . If there is a permutation, print one. If there are multiple possible answers, you may output any one. $ ^{\text{∗}} $ An array $ c $ is a subarray of an array $ d $ if $ c $ can be obtained from $ d $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. $ ^{\text{†}} $ An array $ c $ is lexicographically smaller than an array $ d $ if and only if one of the following holds: - $ c $ is a prefix of $ d $ , but $ c \ne d $ ; or - in the first position where $ c $ and $ d $ differ, the array $ c $ has a smaller element than the corresponding element in $ d $ . $ ^{\text{‡}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2\cdot 10^5 $ ) — denoting the length of the array $ x $ . The following line contains $ n $ integers $ x_1,x_2,\ldots,x_n $ ( $ 1 \leq x_i \leq i $ ) — denoting the array $ x $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, print YES if a permutation exists, and NO otherwise. Each letter may be outputted in uppercase or lowercase. You can output in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. If the answer is positive, output the permutation of $ n $ numbers on the next line.

In the first test case, $ [1,2,3] $ is a valid permutation that satisfies the input array: - for $ [1] $ , there is only one way to partition: partition $ a[1] $ by itself, so $ f([1])=1 $ . - for $ [1,2] $ , there are two ways to partition: $ [1,2] $ by itself or $ [1]+[2] $ . Constructing $ b $ from the first partition yields $ b=[1] $ and constructing $ b $ from the second partition yields $ b=[1,2] $ . The second one is lexicographically larger, so $ f([1,2])=2 $ . - For $ [1,2,3] $ , it can be shown the best partition is $ [1,2]+[3] $ , yielding $ b=[1,3] $ . In the second test case, it can be shown there are no permutations of size $ 2 $ with $ x_1=x_2=1 $ . In the fourth test case, one permutation that satisfies the conditions is $ [3,1,2] $ .