Lexicographically Maximum Cow Sequence

Farmer John has N cows arranged in a queue a. The i-th cow in the queue has an integer label \(a_i\) (\(1 \le a_i \le N\)); cows may share the same label. FJ will construct another queue b by taking cows from a one‐by‐one from the front. When a cow is removed from a, he may choose whether to append it to the end of b.

FJ’s goal is to obtain a sequence \(b\) whose label sequence (from front to back) is lexicographically maximum. (Recall that a sequence \(X\) is lexicographically larger than a sequence \(Y\) if at the first position where they differ, the element in \(X\) is larger; if one sequence is a prefix of the other then the longer sequence is considered larger.)

Prior to constructing queue b, FJ is allowed to perform at most one operation: he may select one cow from queue a and move it to any position before its original position. After this optional move (which may be skipped), FJ processes queue a as described.

Assuming FJ uses the move optimally, output the lexicographically maximum label sequence of b that he can obtain.

Note: Each test case contains a separate instance.

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 100\)), the number of test cases. For each test case:

• The first line contains an integer \(N\) (\(1 \le N \le 2 \cdot 10^5\)).
• The second line contains \(N\) space‐separated integers \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le N\)).

The sum of \(N\) over all test cases does not exceed \(2 \cdot 10^5\).

outputFormat

For each test case, output one line containing the lexicographically maximum sequence obtainable for queue b. Output the numbers separated by a single space.

sample

2
2
1 2
3
2 1 2

2 1
2 2 1