CF1209C Paint the Digits

给定一个长度为 $n$ 的数字序列 $d_1d_2\dots d_n$。你需要将所有数字涂成两种颜色，使得： - 每个数字要么被涂成颜色 $1$，要么被涂成颜色 $2$； - 如果你从左到右依次写下所有被涂成颜色 $1$ 的数字，然后在它们后面写下所有被涂成颜色 $2$ 的数字，那么得到的 $n$ 位数字序列是非递减的（即每个后面的数字都不小于前面的数字）。 例如，对于序列 $d=914$，唯一合法的涂色方案是 $211$（将最后两个数字涂成颜色 $1$，第一个数字涂成颜色 $2$）。但 $122$ 不是合法的涂色方案（$9$ 与 $14$ 拼接后不是非递减序列）。 允许某一种颜色完全不使用。被涂成同一种颜色的数字不要求在原序列中位置连续。 请找出任意一种合法的涂色方案，或者判断是否无法实现。

第一行包含一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$），表示给定数字序列的长度。 接下来一行包含一个长度为 $n$ 的数字序列 $d_1d_2\dots d_n$（$0 \le d_i \le 9$）。数字之间没有空格或其他分隔符，序列可以以 $0$ 开头。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出 $t$ 行，每行对应一个测试用例的答案。 如果存在合法的涂色方案，输出任意一种方案，表示为一个长度为 $n$ 的字符串 $t_1t_2\dots t_n$（$1 \le t_i \le 2$），其中 $t_i$ 表示第 $i$ 个数字被涂成的颜色。如果存在多种方案，输出任意一种即可。 如果不存在合法方案，输出一个字符 '-'（减号）。

在第一个测试用例中，$d=040425524644$。输出 $t=121212211211$ 是合法的，因为 $0022444$（涂成 $1$ 的数字）与 $44556$（涂成 $2$ 的数字）拼接后为 $002244444556$，这是原序列的一个非递减排列。 由 ChatGPT 4.1 翻译