P11839 [USACO25FEB] The Best Lineup S

Farmer John has $N$ $(1 \leq N \leq 2 \cdot 10^5)$ cows in a line $a$. The $i$'th cow from the front of line $a$ is labeled an integer $a_i$ ($1 \leq a_i \leq 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 \leq T \leq 100$) independent test cases.

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 $a_1, a_2, \ldots, a_N$. It is guaranteed that the sum of $N$ over all test cases does not exceed $10^6$.

For each test case, output the lexicographically greatest $b$ on a new line.

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 \leq 100$ - Inputs 5-8: $N \leq 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 $s_i \neq t_i$, $s_i > t_i$. - If no such $i$ exists, $s$ is longer than $t$.