2046: [ USACO 2025 February Contest, Silver] Problem 1. The Best Lineup
题目描述
Farmer John has cows in a line . The 'th cow from the front of line is labeled an integer (). Multiple cows may be labeled the same integer.
FJ will construct another line in the following manner:
- Initially, is empty.
- While is nonempty, remove the cow at the front of and potentially add that cow to the back of .
FJ wants to construct line such that the sequence of labels in from front to back is lexicographically greatest (see the footnote).
Before FJ constructs line , he can perform the following operation at most once:
- Choose a cow in line 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 he can achieve.
Each input will consist of () independent test cases.
输入
The first line of each test case contains .
The second line of each test case contains space-separated integers .
It is guaranteed that the sum of over all test cases does not exceed .
输出
样例输入
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 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.
FOOTNOTE:
Recall that a sequence is lexicographically greater than a sequence if and only if one of the following holds:- At the first position where , .
- If no such exists, is longer than .