Problem E: Peggy hates decreasing

Problem E: Peggy hates decreasing

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2663  Solved: 265
[Submit][Status][Web Board]

Description

Peggy is an aggressive boy, and he hates decreasing. So he wants to delete all decreasing number. He has a sequence {\(a_i\)} of length n, and the definition of decreasing number is the number either the previous one is bigger than it or the next one is smaller than it. In other word, the number of index \(i\) is a decreasing number if and only if \( i > 1 \ \& a[i-1] > a[i] \) or \(i < n \ \& \ a[i] > a[i+1]\) . In every turn he will delete all the decreasing numbers at the same time. And he will repeat the process until there are no elements to delete. Now he asks you what the final sequence is.

Input

The first line of input contains an integer T(1<=T<=10) which is the total number of test cases.

For each test case, there are two lines.

The first line contains a integer n, \(n <= 100000\).

The second line contains n integers, representing the sequence {\(a[i]\)} (1<=\(a_i\)<=100000)


Output

One line per test case, represents the final sequence after Peggy deletes.

Sample Input

2
10
1 4 4 3 2 8 9 4 5 7
5
1 8 6 2 4

Sample Output

1 4 7
1 4

HINT

[Submit][Status]