Mystic Permutation (Codeforces 1689B)
Tags: Greedy, data structures

Monocarp is a little boy who lives in Byteland and he loves programming.Recently, he found a permutation of length $$$n$$$. He has to come up with a mystic permutation. It has to be a new permutation such that it differs from the old one in each position.More formally, if the old permutation is $$$p_1,p_2,\ldots,p_n$$$ and the new one is $$$q_1,q_2,\ldots,q_n$$$ it must hold that $$$$$$p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n.$$$$$$Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?

Input: There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 200$$$) — the number of test cases. This is followed by the test cases description.The first line of each test case contains a positive integer $$$n$$$ ($$$1\leq n\leq 1000$$$) — the length of the permutation.The second line of each test case contains $$$n$$$ distinct positive integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). It's guaranteed that $$$p$$$ is a permutation, i. e. $$$p_i \neq p_j$$$ for all $$$i \neq j$$$. It is guaranteed that the sum of $$$n$$$ does not exceed $$$1000$$$ over all test cases.

Output: For each test case, output $$$n$$$ positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output $$$-1$$$ instead.

Note: In the first test case possible permutations that are mystic are $$$[2,3,1]$$$ and $$$[3,1,2]$$$. Lexicographically smaller of the two is $$$[2,3,1]$$$.In the second test case, $$$[1,2,3,4,5]$$$ is the lexicographically minimal permutation and it is also mystic.In third test case possible mystic permutations are $$$[1,2,4,3]$$$, $$$[1,4,2,3]$$$, $$$[1,4,3,2]$$$, $$$[3,1,4,2]$$$, $$$[3,2,4,1]$$$, $$$[3,4,2,1]$$$, $$$[4,1,2,3]$$$, $$$[4,1,3,2]$$$ and $$$[4,3,2,1]$$$. The smallest one is $$$[1,2,4,3]$$$.

Sample Inputs:
4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1

Sample Outputs:
2 3 1
1 2 3 4 5
1 2 4 3
-1

Solution (Python):
num_test_cases = int(input())
for _ in range(num_test_cases):
    n = int(input())
    permutation = list(map(int, input().split()))
    sorted_permutation = sorted(permutation)
    for i in range(n - 1):
        if sorted_permutation[i] == permutation[i]:
            (sorted_permutation[i], sorted_permutation[i + 1]) = (sorted_permutation[i + 1], sorted_permutation[i])
    if n == 1:
        sorted_permutation = [-1]
    elif sorted_permutation[-1] == permutation[-1]:
        (sorted_permutation[-1], sorted_permutation[-2]) = (sorted_permutation[-2], sorted_permutation[-1])
    print(*sorted_permutation)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    if n == 1:
        print(-1)
        continue
    sarr = sorted(arr)[:]
    for i in range(n - 1):
        if sarr[i] == arr[i]:
            (sarr[i], sarr[i + 1]) = (sarr[i + 1], sarr[i])
    if sarr[-1] == arr[-1]:
        (sarr[-1], sarr[-2]) = (sarr[-2], sarr[-1])
    print(*sarr)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    if len(arr) == 1:
        print(-1)
        continue
    sarr = sorted(arr)
    for i in range(n - 1):
        if sarr[i] == arr[i]:
            (sarr[i], sarr[i + 1]) = (sarr[i + 1], sarr[i])
    if sarr[-1] == arr[-1]:
        (sarr[-1], sarr[-2]) = (sarr[-2], sarr[-1])
        if sarr[-2] != arr[-2] and sarr[-1] != arr[-1]:
            print(*sarr)
        else:
            print(-1)
    else:
        print(*sarr)