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

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

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.

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.

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

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

提交代码