CF1144G Two Merged Sequences

最初存在两个整数序列，其中一个是严格递增的，另一个是严格递减的。 严格递增序列是整数序列 $[x_1 < x_2 < \dots < x_k]$。严格递减序列是整数序列 $[y_1 > y_2 > \dots > y_l]$。注意，空序列和只包含一个元素的序列也可以视为递增或递减序列。 递增序列的元素被插入到递减序列的元素之间（也可能插入到递减序列的第一个元素之前或最后一个元素之后），且不改变递增序列和递减序列各自的顺序。例如，序列 $[1, 3, 4]$ 和 $[10, 4, 2]$ 可以生成如下结果序列：$[10, \textbf{1}, \textbf{3}, 4, 2, \textbf{4}]$，$[\textbf{1}, \textbf{3}, \textbf{4}, 10, 4, 2]$。但如下序列不能作为插入结果：$[\textbf{1}, 10, \textbf{4}, 4, \textbf{3}, 2]$，因为递增序列的元素顺序被改变了。 设最终得到的序列为 $a$。该序列 $a$ 已在输入中给出。你的任务是找出任意一组符合要求的初始序列，其中一个为严格递增序列，另一个为严格递减序列。注意，空序列和只包含一个元素的序列也可以视为递增或递减序列。 如果输入存在矛盾，无法将给定序列 $a$ 拆分为一个递增序列和一个递减序列，请输出 "NO"。

输入的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示序列 $a$ 的元素个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2 \cdot 10^5$），其中 $a_i$ 表示 $a$ 的第 $i$ 个元素。

如果输入存在矛盾，无法将给定序列 $a$ 拆分为一个递增序列和一个递减序列，第一行输出 "NO"。 否则，第一行输出 "YES"。第二行输出 $n$ 个整数 $res_1, res_2, \dots, res_n$，其中 $res_i$ 为 $0$ 或 $1$。如果 $a$ 的第 $i$ 个元素属于递增序列，则 $res_i = 0$，否则 $res_i = 1$。注意，空序列和只包含一个元素的序列也可以视为递增或递减序列。

由 ChatGPT 4.1 翻译