# 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

• `\$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\$`

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

### Statistics

0% Solution Ratio