CF2259D.MEX Multiset

You are given an array $a_1, a_2, \ldots, a_n$. There exist $3$ initially empty multisets $A, B, C$, and for each index $i$ ($1 \leq i \leq n$), you may put $a_i$ into exactly one of $A$, $B$, or $C$.

Determine whether it is possible to put the elements into the multisets such that $\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) \geq 2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C))$$^{\text{∗}}$. If so, output a construction that achieves this.

$^{\text{∗}}$$\operatorname{MEX}(D)$ is defined as the smallest non-negative integer that is not present in the set $D$. For example, $\operatorname{MEX}([1, 2, 0, 5]) = 3$, and $\operatorname{MEX}([1, 2, 4, 9]) = 0$. The $\operatorname{MEX}$ of an empty set is $0$.

给你一个数组 $a_1, a_2, \ldots, a_n$。存在三个初始为空的多重集 $A, B, C$，对于每个下标 $i$（$1 \leq i \leq n$），你可以将 $a_i$ 恰好放入 $A$、$B$ 或 $C$ 中的一个。

判断是否可能将所有元素分配到这三个多重集中，使得

$$\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) \geq 2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C))$$

成立。若可行，请输出一种满足条件的分配方案。

$^{\text{∗}}$ $\operatorname{MEX}(D)$ 定义为集合 $D$ 中未出现的最小非负整数。例如，$\operatorname{MEX}([1, 2, 0, 5]) = 3$，而 $\operatorname{MEX}([1, 2, 4, 9]) = 0$。空集的 $\operatorname{MEX}$ 为 $0$。

The first line of each input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of $a$.

The second line of each test case contains $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每组输入的第一行包含 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。

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

每个测试用例的第二行包含 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）—— 数组 $a$。

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

If a valid distribution of elements into the multisets exists, output $\texttt{YES}$. Otherwise, output $\texttt{NO}$.

If the answer is $\texttt{YES}$, output a string $s$ of length $n$ on a new line, such that $s_i = \texttt{A}$ if the $i$-th element was put into the multiset $A$, $s_i = \texttt{B}$ if the $i$-th element was put into the multiset $B$, and $s_i = \texttt{C}$ if the $i$-th element was put into the multiset $C$.

You can output the answer in any case (upper or lower). For example, the strings $\texttt{YES}$, $\texttt{yes}$, $\texttt{yEs}$, and $\texttt{Yes}$ will be recognized as positive responses, and the strings $\texttt{NO}$, $\texttt{no}$, $\texttt{No}$ will be recognized as negative responses. Additionally, the strings $\texttt{AABCAAA}$, $\texttt{aabcaaa}$, and $\texttt{aaBcaaa}$ will be recognized as the same answer.

If there are multiple possible outputs, output any.

如果存在一种将元素分配到多重集的合法方案，则输出 $\texttt{YES}$；否则输出 $\texttt{NO}$。

若答案为 $\texttt{YES}$，则在下一行输出一个长度为 $n$ 的字符串 $s$，其中：若第 $i$ 个元素被放入多重集 $A$，则 $s_i = \texttt{A}$；若被放入多重集 $B$，则 $s_i = \texttt{B}$；若被放入多重集 $C$，则 $s_i = \texttt{C}$。

答案大小写不限。例如，字符串 $\texttt{YES}$、$\texttt{yes}$、$\texttt{yEs}$ 和 $\texttt{Yes}$ 均被视为肯定回答；字符串 $\texttt{NO}$、$\texttt{no}$、$\texttt{No}$ 均被视为否定回答。此外，字符串 $\texttt{AABCAAA}$、$\texttt{aabcaaa}$ 和 $\texttt{aaBcaaa}$ 将被视为同一答案。

若存在多种可能的输出，输出任意一种即可。

In the first test case, we can have $A = {0, 1, 1}$, $B = {0, 1}$, $C = {2}$, meaning $\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) = 4$, and $2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C)) = 2 \cdot \max(2, 2, 0) = 4$.

In the third test case, it can be shown that there are no valid distributions.

在第一个测试用例中，我们可以取 $A = \{0, 1, 1\}$，$B = \{0, 1\}$，$C = \{2\}$，此时有 $\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) = 4$，且 $2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C)) = 2 \cdot \max(2, 2, 0) = 4$。

在第三个测试用例中，可以证明不存在合法的划分方案。