Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Next Permutation

By solaimanope · Limits 3s, 1.0 GB

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)$.

Input

  • The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
  • The first line of each test case contains one integer $N$.
  • The second line contains $N$ space-separated integers $P_1,P_2,\dots, P_N$.

Constraints

  • Subtask 1 (3 points)
    • $1 \le T \le 5×10^5$
    • $1 \le N \le 9$
  • Subtask 2 (13 points)
    • $1 \le T \le 10^4$
    • $1 \le N \le 100$
  • Subtask 3 (27 points)
    • $1 \le T \le 400$
    • $1 \le N \le 400$
  • Subtask 4 (16 points)
    • $1 \le T \le 100$
    • $1 \le N \le 2000$
  • Subtask 5 (41 points)
    • $1 \le T \le 50$
    • $1 \le N \le 10^5$

Output

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$.

Sample

InputOutput
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.

Discussion

Statistics


0% Solution Ratio

Submit

Login to submit

Editorial

There is Bangla editorial too. For subtask 1: For subtask 1 we will generate all possible permuati...