D. Dividing Sequence
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 sequence $$$A$$$.
  • 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 \lt 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 \lt k$$$ and $$$p_k \lt 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$$$.

Input

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$$$.

Output

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$$$.

Example
Input
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
Output
1
3
3
1 1 2
2
3 3
3
1 3 1
4
2 1 3 3