CF1144C Two Shuffled Sequences

最初存在两个整数序列——其中一个是严格递增的，另一个是严格递减的。 严格递增序列是一个整数序列 $[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" 的情况下）。

由 ChatGPT 4.1 翻译