The Best Lineup

문제

Farmer John has $NN$ $(1\le N\le 2\cdot {10}^5)(1\; \backslash leq\; N\; \backslash leq\; 2\; \backslash cdot\; 10^5)$ cows in a line $aa$. The $ii$'th cow from the front of line $aa$ is labeled an integer $a_{i}a\_i$ ($1\le a_i\le N1\; \backslash leq\; a\_i\; \backslash leq\; N$). Multiple cows may be labeled the same integer.

FJ will construct another line $bb$ in the following manner:

• Initially, $bb$ is empty.
• While $aa$ is nonempty, remove the cow at the front of $aa$ and potentially add that cow to the back of $bb$.

FJ wants to construct line $bb$ such that the sequence of labels in $bb$ from front to back is lexicographically greatest (see the footnote).

Before FJ constructs line $bb$, he can perform the following operation at most once:

• Choose a cow in line $aa$ 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 $bb$ he can achieve.

Each input will consist of $TT$ ($1\le T\le 1001\; \backslash leq\; T\; \backslash leq\; 100$) independent test cases.

입력

The first line contains $TT$.

The first line of each test case contains $NN$.

The second line of each test case contains $NN$ space-separated integers $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash ldots,\; a\_N$.

It is guaranteed that the sum of $NN$ over all test cases does not exceed ${10}^{6}10^6$.

출력

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

힌트

Recall that a sequence $ss$ is lexicographically greater than a sequence $tt$ if and only if one of the following holds:

• At the first position $ii$ where $s_i\mathrm{\ne }{t}_{i}s\_i\; \backslash neq\; t\_i$, $s_i>t_{i}s\_i\; >\; t\_i$.
• If no such $ii$ exists, $ss$ is longer than $tt$.

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