#214288. [ICPC 2024 Hangzhou R] Dividing Sequence

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

• and are both subsequences of - Each element of belongs to exactly one of the sequences or .
• in lexicographical order.

Here we define a sequence of length to be lexicographically smaller than a sequence of length if one of the following constraints is true:

• and is a prefix of .
• There exists an integer such that for all and .

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

There are multiple test cases. The first line of the input contains an integer () indicating the number of test cases. For each test case:

The first line contains an integer () indicating the length of the sequence .

The second line contains integers (), where is the -th element of sequence .

It is guaranteed that the sum of of all test cases does not exceed .

For each test case output two lines. First output one line containing one integer indicating the length of the optimal . Then output a second line containing integers separated by a space, where is the -th element of the optimal .

样例输入 1

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

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