silver_The_Best_Lineup (USACO February_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: data structures, greedy, stack, segment tree

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

Starter code:

Grader code:

Setup script:

Evaluation script: