CF1144G.Two Merged Sequences

Two integer sequences existed initially, one of them was strictly increasing, and another one — strictly decreasing.

Strictly increasing sequence is a sequence of integers $[x_1 \lt x_2 \lt \dots \lt x_k]$. And strictly decreasing sequence is a sequence of integers $[y_1 \gt y_2 \gt \dots \gt y_l]$. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

Elements of increasing sequence were inserted between elements of the decreasing one (and, possibly, before its first element and after its last element) without changing the order. For example, sequences $[1, 3, 4]$ and $[10, 4, 2]$ can produce the following resulting sequences: $[10, \textbf{1}, \textbf{3}, 4, 2, \textbf{4}]$, $[\textbf{1}, \textbf{3}, \textbf{4}, 10, 4, 2]$. The following sequence cannot be the result of these insertions: $[\textbf{1}, 10, \textbf{4}, 4, \textbf{3}, 2]$ because the order of elements in the increasing sequence was changed.

Let the obtained sequence be $a$. This sequence $a$ is given in the input. Your task is to find any two suitable initial sequences. One of them should be strictly increasing, and another one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

If there is a contradiction in the input and it is impossible to split the given sequence $a$ into one increasing sequence and one decreasing sequence, print "NO".

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

严格递增序列是指整数序列 $[x_1 \lt x_2 \lt \dots \lt x_k]$；严格递减序列是指整数序列 $[y_1 \gt y_2 \gt \dots \gt 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"。

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the $i$-th element of $a$.

输入的第一行包含一个整数 $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$ 个元素。

If there is a contradiction in the input and it is impossible to split the given sequence $a$ into one increasing sequence and one decreasing sequence, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line, print a sequence of $n$ integers $res_1, res_2, \dots, res_n$, where $res_i$ should be either $0$ or $1$ for each $i$ from $1$ to $n$. The $i$-th element of this sequence should be $0$ if the $i$-th element of $a$ belongs to the increasing sequence, and $1$ otherwise. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

如果输入中存在矛盾，无法将给定序列 $a$ 拆分为一个递增序列和一个递减序列，则在第一行输出 "NO"。

否则，在第一行输出 "YES"。在第二行输出一个由 $n$ 个整数构成的序列 $res_1, res_2, \dots, res_n$，其中对每个 $i$（$1$ 到 $n$），$res_i$ 应为 $0$ 或 $1$。该序列的第 $i$ 个元素应为 $0$，当且仅当 $a$ 的第 $i$ 个元素属于递增序列；否则为 $1$。注意：空序列以及仅含一个元素的序列既可视为递增序列，也可视为递减序列。