P14190 [ICPC 2024 Hangzhou R] Dividing Sequence

Alice 收到了一串由她的邻居们构造的序列 $A$。由于 Alice 不喜欢过长的序列，她决定将序列分成两个（可能为空）序列 $B$ 和 $C$，再还给她的邻居们。她分割的方式需要满足以下约束条件： - $B$ 和 $C$ 都是 $A$ 的子序列，且 $A$ 的每一个元素都会被分配到 $B$ 或 $C$ 中的恰好一个序列。 - $B$ 在字典序上小于等于 $C$。 在这里，我们定义长度为 $u$ 的序列 $P = p_1, p_2, \cdots, p_u$ 在字典序上小于长度为 $v$ 的序列 $Q = q_1, q_2, \cdots, q_v$，当且仅当满足下列条件之一： - $u < v$ 且 $P$ 是 $Q$ 的前缀。 - 存在整数 $1 \le k \le \min(u, v)$，使得对于所有 $1 \le i < k$ 有 $p_i = q_i$ 且 $p_k < q_k$。 作为一位公平的女孩，Alice 希望分得公平，使得 $C$ 的字典序尽可能小。请你告诉 Alice，$C$ 能取得的字典序最小的情况。

有多组测试数据。输入的第一行包含一个整数 $T$（$1\leq T\leq 10^4$），表示测试数据组数。对于每组测试数据： 第一行包含一个整数 $n$（$1\leq n\leq 5 \times 10^3$），表示序列 $A$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1\leq a_i\leq 10^5$），表示序列 $A$ 的第 $i$ 个元素。 保证所有测试数据中 $n$ 的总和不超过 $10^4$。

对于每组测试数据，输出两行。第一行包含一个整数 $m$，表示最优情况下 $C$ 的长度。第二行包含 $m$ 个用空格分隔的整数 $c_1, c_2, \cdots, c_m$，表示最优情况下 $C$ 的序列。

由 ChatGPT 5 翻译