Farmer John has N (1≤N≤2⋅105) cows in a line a. The i'th cow from the front of line a is labeled an integer ai (1≤ai ≤N). Multiple cows may be labeled the same integer.
FJ 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 potentially add that cow to the back of b.
FJ wants to construct line b such that the sequence of labels in b from front to back is lexicographically greatest (see the footnote).
Before FJ constructs line b, he can perform the following operation at most once:
Choose a cow in line a and move it anywhere before its current position.
Given that FJ optimally performs the aforementioned operation at most once, output the lexicographically greatest label sequence of b he can achieve.
Each input will consist of T (1≤T≤100) independent test cases.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T.
The first line of each test case contains N.
The second line of each test case contains N space-separated integers a1,a2,…,aN.
It is guaranteed that the sum of N over all test cases does not exceed 106.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output the lexicographically greatest b on a new line.
SAMPLE INPUT:
3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 1
SAMPLE OUTPUT:
4 3 3 2 1
6 5 4
4 3 2 1 1
In the first test case, FJ can move the fifth cow to directly after the second cow. Now, a=[4,3,3,2,1]. It can be shown [4,3,3,2,1] is also the lexicographically greatest b.
In the second test case, FJ can move the fourth cow to the front of the line.
In the third test case, FJ does not need to perform any operations. He can construct b by adding each cow beside the second cow to the back of b. It can be shown this results in the lexicographically greatest b.
SCORING:
Inputs 2-4: N≤100
Inputs 5-8: N≤750
Inputs 9-18: No additional constraints
FOOTNOTE:
Recall that a sequence s is lexicographically greater than a sequence t if and only if one of the following holds:
At the first position i where si≠ti, si>si.
If no such i exists, s is longer than t.
Problem credits: Chongtian Ma, Haokai Ma, Andrew Li
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
