#PU1494. USACO 2025 February Contest, Silver — Problem 1. The Best Lineup
USACO 2025 February Contest, Silver — Problem 1. The Best Lineup
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,
输入格式
The first line contains . 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 .
输出格式
For each test case, output the lexicographically greatest on a new line.
数据范围
Inputs 2-4: Inputs 5-8: Inputs 9-18: No additional constraints 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 . Problem credits: Chongtian Ma, Haokai Ma, Andrew Li
样例
样例 1
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, 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$.