Description

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$ 能取得的字典序最小的情况。

Input Format

有多组测试数据。输入的第一行包含一个整数 $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$。

Output Format

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

5
5
3 1 2 3 2
3
1 1 2
3
3 3 3
5
1 3 1 3 1
5
2 2 1 3 3

1
3
3
1 1 2
2
3 3
3
1 3 1
4
2 1 3 3

Hint

由 ChatGPT 5 翻译