Brute Force Sorting

Time Limit: 1000/1000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

Description

Beerus needs to sort an array of $N$ integers. Algorithms are not Beerus's strength. Destruction is what he excels. He can destroy all unsorted numbers in the array simultaneously. A number $A[i]$ of the array is sorted if it satisfies the following requirements.
1. $A[i]$ is the first element of the array, or it is no smaller than the left one $A[i-1]$.
2. $A[i]$ is the last element of the array, or it is no bigger than the right one $A[i+1]$.
In $[1,4,5,2,3]$, for instance, the element $5$ and the element $2$ would be destoryed by Beerus. The array would become $[1,4,3]$. If the new array were still unsorted, Beerus would do it again.
Help Beerus predict the final array.

Input

The first line of input contains an integer $T~(1\le T\le 10)$ which is the total number of test cases.
For each test case, the first line provides the size of the inital array which would be positive and no bigger than $100000$.
The second line describes the array with $N$ positive integers $A[1],A[2],\cdots,A[N]$ where each integer $A[i]$ satisfies $1\le A[i]\le 100000$.

Output

For eact test case output two lines.
The first line contains an integer $M$ which is the size of the final array.
The second line contains $M$ integers describing the final array.
If the final array is empty, $M$ should be $0$ and the second line should be an empty line.

Sample Input

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

Sample Output

5 1 2 3 4 5 0 2 1 2 2 1 3 3 2 3 5

Hint

liuyiding

Source

2017 ACM/ICPC Asia Regional Qingdao Online

提交代码