Problems
Farmer John has N cows (1 ≤ N ≤ 2⋅10⁵) arranged in a line, denoted as a. The i-th cow from the front of line a is labeled with an integer aᵢ (1 ≤ aᵢ ≤ N). Multiple cows may share the same label.
Farmer John will construct another line, b, in the following manner:
Initially, b is empty.
While a is nonempty, remove the cow at the front of a and decide whether to add that cow to the back of b.
John wants to construct line b such that the sequence of labels in b, read from front to back, is lexicographically greatest.
Before constructing b, John may perform the following operation at most once:
Choose a cow in line a and move it to any position before its current position.
Given that John performs this operation optimally at most once, output the lexicographically greatest label sequence of b he can achieve.
Each input consists of T (1 ≤ T ≤ 100) independent test cases.
Input
The first line contains an integer T, the number of test cases.
For each test case, the first line contains an integer N.
The second line of each test case contains N space-separated integers a₁, a₂, …, aₙ, representing the labels on the cows.
It is guaranteed that the sum of N over all test cases does not exceed 10⁶.
Output
For each test case, output the lexicographically greatest b sequence on a new line, with each number separated by a space.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 20 | |
| #2 | 30 | |
| #3 | 50 | No additional constraints |
Example
3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 1
4 3 3 2 1
6 5 4
4 3 2 1 1
In the first test case, John can move the fifth cow to directly after the second cow. This transforms a into [4, 3, 3, 2, 1], which is the lexicographically greatest b sequence.
In the second test case, John can move the fourth cow to the front of the line to achieve the optimal b sequence.
In the third test case, no operation is needed; simply appending the cows from a into b in order yields the lexicographically greatest b sequence.
You must sign in to write code.