A sequence of $N$ distinct integers is called a permutation if all the integers are between $1$ and $N$ (inclusive).
We define descent of a permutation as the number of positions in the permutation where an element is greater than the next element. For example, descent of permutation $(1, 2, 3, 4, 5)$ is $0$, descent of permutation $(4, 2, 1, 3, 5)$ is $2$ (since $4$ is greater than $2$ and $2$ is greater than $1$), descent of permutation $(5, 4, 3, 2, 1)$ is $4$. As you can see, the descent of an $N$ element permutation can be at most $N-1$.
You are given a $N$ element permutation $P$. You have to find the lexicographically smallest $N$ element permutation $Q$ which is lexicographically greater than $P$ and descent of $Q$ is the same as that of $P$. If such a permutation does not exist, you have to report that.
An $N$ element permutation $A$ is lexicographically smaller than an $N$ element permutation $B$ if there exists an index $i$ $(1 \le i \le N)$ such that $A_i < B_i$ and for each $j$ $(1 \le j \lt i)$, $A_j = B_j$. For example, $(3, 4, 1, 2, 5)$ is lexicographically smaller than $(4, 1, 2, 5, 3)$; $(2, 1, 3, 5, 4)$ is lexicographically smaller than $(2, 1, 4, 3, 5)$.
$T$ denoting the number of test cases. The description of $T$ test cases follows.$N$.$N$ space-separated integers $P_1,P_2,\dots, P_N$.$1 \le T \le 5×10^5$$1 \le N \le 9$$1 \le T \le 10^4$$1 \le N \le 100$$1 \le T \le 400$$1 \le N \le 400$$1 \le T \le 100$$1 \le N \le 2000$$1 \le T \le 50$$1 \le N \le 10^5$For each test case, if such a permutation $Q$ does not exist, print a line containing the integer $-1$. Otherwise, print a line containing $N$ space-separated integers denoting the elements of $Q$.
| Input | Output |
|---|---|
3 3 1 2 3 3 1 3 2 5 5 2 1 3 4 | -1 2 1 3 5 2 3 1 4 |
The input/output files are huge. Use faster IO operations i.e. printf/scanf in C/C++ or similar.