P14066 [PO Final 2022] 分组 / Triangeltal

在一所班级里有 $N$ 名学生，现在到了必须进行的演讲环节。大多数学生都非常期待演讲，恨不得立刻轮到自己。但在此之前，需要先把他们分成 3 个小组。随后，组 1 的所有人会向组 2 演讲，组 2 向组 3 演讲，组 3 向组 1 演讲。 让分组变得复杂的是，学生的追求程度不同。每位学生 $i$ 要求自己至少要在 $A_i$ 位听众面前演讲，其中 $A_i$ 为正整数。举例而言，如果学生 $i$ 被分到组 1，那么为了让学生 $i$ 满意，组 2 必须至少有 $A_i$ 名成员。这个要求对三组按循环关系成立： * 若学生 $i$ 在第 1 组，则第 2 组的人数至少为 $A_i$。 * 若学生 $i$ 在第 2 组，则第 3 组的人数至少为 $A_i$。 * 若学生 $i$ 在第 3 组，则第 1 组的人数至少为 $A_i$。 给定这 $N$ 个数 $A_i$，你的任务是判断是否存在一种把学生分成三组的方法，使得所有学生都满意；如果存在，请找出一种合法的分组。

第一行包含一个整数 $N$（$3 \le N \le 5 \cdot 10^5$）。 第二行包含 $N$ 个整数 $A_i$（$1 \le A_i \le N$）。

如果不存在合法分组，输出仅包含字符串 $\texttt{NO}$ 的一行。 如果存在合法分组，先输出一行字符串 $\texttt{YES}$。随后输出一行字符串 $S$，它由字符 1、2 和 3 组成。字符串中第 $i$ 个位置的字符表示学生 $i$ 被分到了哪一组。如果有多种解，输出任意一种均可。

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $14$ | $A_1 = A_2 = \dots = A_N$ | | $2$ | $16$ | $N \le 10$ | | $3$ | $11$ | $A_i \le 3$ | | $3$ | $23$ | $N \le 3000$ | | $4$ | $36$ | 无额外限制 |