P14190 [ICPC 2024 Hangzhou R] Dividing Sequence

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