CF2001D Longest Max Min Subsequence

给定一个整数序列 $a_1, a_2, \ldots, a_n$。设 $S$ 为所有可能的不含重复元素的非空子序列的集合。你的目标是找到 $S$ 中最长的序列。如果有多个这样的序列，要求在将奇数位置的元素乘以 $-1$ 后，字典序最小的那个。 例如，给定 $a = [3, 2, 3, 1]$，$S = \{[1], [2], [3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 3, 1], [3, 2, 1]\}$。那么 $[2, 3, 1]$ 和 $[3, 2, 1]$ 是最长的序列，而 $[3, 2, 1]$ 是答案，因为 $[-3, 2, -1]$ 的字典序比 $[-2, 3, -1]$ 小。 如果序列 $c$ 可以通过从序列 $d$ 中删除若干（可能为零或全部）元素得到，则称 $c$ 是 $d$ 的一个子序列。 如果满足以下任一条件，则称序列 $c$ 的字典序小于序列 $d$： - $c$ 是 $d$ 的前缀，且 $c \ne d$； - 在 $c$ 和 $d$ 第一个不同的位置，$c$ 的元素小于 $d$ 对应位置的元素。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 5 \cdot 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示序列 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示序列 $a$。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出答案，格式如下： 第一行输出一个整数 $m$，表示序列 $b$ 的长度。 第二行输出 $m$ 个整数 $b_1, b_2, \ldots, b_m$，表示序列 $b$。

在第一个样例中，$S = \{[1], [2], [3], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 1, 3], [3, 2, 1]\}$。其中 $[2, 1, 3]$ 和 $[3, 2, 1]$ 是最长的序列，$[-3, 2, -1]$ 的字典序比 $[-2, 1, -3]$ 小，所以 $[3, 2, 1]$ 是答案。 在第二个样例中，$S = \{[1]\}$，所以 $[1]$ 是答案。 由 ChatGPT 4.1 翻译