题目描述

Alice got a sequence $A$ constructed by her neighbors. Since Alice doesn't like long sequences, she decides to divide the sequence into two (possibly empty) sequences $B$ and $C$ and give them back to her neighbors. Her division should meet the following constraints:

• $B$ and $C$ are both subsequences of - Each element of $A$ belongs to exactly one of the sequences $B$ or $C$.
• $B\leq C$ in lexicographical order.

Here we define a sequence $P = p_1, p_2, \cdots, p_u$ of length $u$ to be lexicographically smaller than a sequence $Q = q_1, q_2, \cdots, q_v$ of length $v$ if one of the following constraints is true:

• $u < v$ and $P$ is a prefix of $Q$.
• There exists an integer $1 \le k \le \min(u, v)$ such that $p_i = q_i$ for all $1 \le i < k$ and $p_k < q_k$.

As a fair girl, Alice hopes to divide fairly such that the lexicographical order of $C$ is as small as possible. Please tell Alice the minimum possible $C$.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ ($1\leq T\leq 10^4$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1\leq n\leq 5 \times 10^3$) indicating the length of the sequence $A$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1\leq a_i\leq 10^5$), where $a_i$ is the $i$-th element of sequence $A$.

It is guaranteed that the sum of $n$ of all test cases does not exceed $10^4$.

输出格式

For each test case output two lines. First output one line containing one integer $m$ indicating the length of the optimal $C$. Then output a second line containing $m$ integers $c_1, c_2, \cdots, c_m$ separated by a space, where $c_i$ is the $i$-th element of the optimal $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