← 返回题目列表

Codeforces · 1144/C

C. 两个打乱的序列

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

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

严格递增序列是整数序列 $$$[x_1 < x_2 < \dots < x_k]$$$。严格递减序列是整数序列 $$$[y_1 > y_2 > \dots > y_l]$$$。注意,空序列和由一个元素组成的序列可以认为是递增或递减。

它们被合并成一个序列$$$a$$$。在这个序列之后,$$$a$$$ 被洗牌了。例如,递增序列 $$$[1, 3, 4]$$$ 和递减序列 $$$[10, 4, 2]$$$ 的一些可能结果序列 $$$a$$$ 是序列 $$$[1, 2, 3, 4, 4, 10]$$$ 或 $$$[4, 2, 1, 10, 4, 3]$$$。

这个打乱序列 $$$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_i$$$ — 严格递增序列中的元素数量。 $$$n_i$$$ 可以为零,在这种情况下递增序列为空。

在第三行中按其值的递增顺序打印 $$$n_i$$$ 整数 $$$inc_1, inc_2, \dots, inc_{n_i}$$$ ($$$inc_1 < inc_2 < \dots < inc_{n_i}$$$) — 严格递增序列本身。如果 $$$n_i = 0$$$ 则可以将此行保留为空(或者只打印空行)。

在第四行中打印 $$$n_d$$$ — 严格递减序列中的元素数量。 $$$n_d$$$ 可以为零,在这种情况下,递减序列为空。

在第五行中按其值的降序打印 $$$n_d$$$ 整数 $$$dec_1, dec_2, \dots, dec_{n_d}$$$ ($$$dec_1 > dec_2 > \dots > dec_{n_d}$$$) — 严格递减序列本身。如果 $$$n_d = 0$$$ (或者只打印空行),则可以将此行保留为空。

$$$n_i + n_d$$$ 应等于 $$$n$$$ 并且打印序列的并集应是给定序列的排列(如果答案为“YES”)。

示例

输入 #1

7
7 2 7 3 3 1 4

输出 #1

YES
2
3 7 
5
7 4 3 2 1

输入 #2

5
4 3 1 5 3

输出 #2

YES
1
3 
4
5 4 3 1

输入 #3

5
1 1 2 1 2

输出 #3

NO

输入#4

5
0 1 2 3 4

输出#4

YES
0

5
4 3 2 1 0