CF2124I.Lexicographic Partition

给定一个数组 $ a $，定义 $ f(a) $ 如下：

• 设 $ k $ 是一个整数，满足 $ 1 \leq k \leq n $。
• 将 $ a $ 划分为 $ k $ 个子数组 $ ^{\text{∗}} $ $ s_1,s_2,\ldots,s_k $，使得 $ s_1+s_2+\ldots+s_k=a $。这里的 $ + $ 表示数组连接。
• 设 $ b $ 是一个空数组。对于每个 $ i $ 从 $ 1 $ 到 $ k $ 依次进行，将 $ s_i $ 的最小元素添加到 $ b $ 的末尾。
• 在所有可能的 $ k $ 和划分中，$ f(a) $ 是使得存在一个划分能够产生字典序最大的 $ b $ $ ^{\text{†}} $ 的 $ k $ 值。

给定 $ n $ 个整数 $ x_1,x_2,\ldots,x_n $。请判断是否存在一个排列 $ ^{\text{‡}} $ $ a $，使得对于每个 $ 1 \leq i \leq n $，有 $ f([a_1,a_2,\ldots,a_i])=x_i $。如果存在这样的排列，输出一个。如果有多个可能的答案，可以输出任意一个。

$ ^{\text{∗}} $ 数组 $ c $ 是数组 $ d $ 的子数组，当且仅当 $ c $ 可以通过从 $ d $ 的开头删除若干个（可能为零或全部）元素和从 $ d $ 的末尾删除若干个（可能为零或全部）元素得到。

$ ^{\text{†}} $ 数组 $ c $ 字典序小于数组 $ d $，当且仅当以下条件之一成立：

• $ c $ 是 $ d $ 的前缀，但 $ c \ne d $；或者
• 在 $ c $ 和 $ d $ 第一个不同的位置，$ c $ 的元素小于 $ d $ 的对应元素。

$ ^{\text{‡}} $ 一个长度为 $ n $ 的排列是一个由 $ 1 $ 到 $ n $ 的 $ n $ 个不同整数按任意顺序组成的数组。例如，$ [2,3,1,5,4] $ 是一个排列，但 $ [1,2,2] $ 不是排列（因为 $ 2 $ 出现了两次），$ [1,3,4] $ 也不是排列（因为 $ n=3 $ 但出现了 $ 4 $）。

每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $（$ 1 \le t \le 10^4 $）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $（$ 2 \leq n \leq 2\cdot 10^5 $）——表示数组 $ x $ 的长度。

接下来的一行包含 $ n $ 个整数 $ x_1,x_2,\ldots,x_n $（$ 1 \leq x_i \leq i $）——表示数组 $ x $。

保证所有测试用例的 $ n $ 之和不超过 $ 2\cdot 10^5 $。

对于每个测试用例，如果存在满足条件的排列，输出 YES，否则输出 NO。字母可以大写或小写。可以以任何大小写形式输出（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定的回答）。

如果答案是肯定的，在下一行输出一个 $ n $ 个数的排列。

在第一个测试用例中，$ [1,2,3] $ 是一个满足输入数组的有效排列：

• 对于 $ [1] $，只有一种划分方式：将 $ a[1] $ 单独划分为一个子数组，所以 $ f([1])=1 $。
• 对于 $ [1,2] $，有两种划分方式：$ [1,2] $ 单独划分为一个子数组，或者 $ [1]+[2] $。从第一种划分得到的 $ b=[1] $，从第二种划分得到的 $ b=[1,2] $。第二种划分的字典序更大，所以 $ f([1,2])=2 $。
• 对于 $ [1,2,3] $，可以证明最优的划分是 $ [1,2]+[3] $，得到的 $ b=[1,3] $。

在第二个测试用例中，可以证明不存在大小为 $ 2 $ 的排列满足 $ x_1=x_2=1 $。

在第四个测试用例中，一个满足条件的排列是 $ [3,1,2] $。

---

翻译来源于 yanrs1019。