문제

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.

예제 입력 1

3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 1

예제 출력 1

4 3 3 2 1
6 5 4
4 3 2 1 1

점수

Inputs 2-4: $N \leq 100$ Inputs 5-8: $N \leq 750$ Inputs 9-18: No additional constraints