# Practice on Toph

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

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

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

.

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

.

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

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

0% Solution Ratio

Login to submit

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