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.