← 返回题目列表

Codeforces · 1144/G

G. 两个合并序列

中文机器翻译题面 查看原题

最初存在两个整数序列,其中一个严格递增,另一个严格递减。

严格递增序列是整数序列 $$$[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$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 应该是 $$$0$$$ 或 $$$1$$$。如果 $$$a$$$ 的第 $$$i$$$ 个元素属于递增序列,则该序列的第 $$$i$$$ 个元素应为 $$$0$$$,否则为 $$$1$$$。注意,空序列和由一个元素组成的序列可以认为是递增或递减。

示例

输入 #1

9
5 1 3 6 8 2 9 0 10

输出 #1

YES
1 0 0 0 0 1 0 1 0

输入 #2

5
1 2 4 0 2

输出 #2

NO