Problem:


Score : 800 points

Problem Statement

Niwango has N cards, numbered 1,2,\ldots,N.
He will now arrange these cards in a row.

Niwango wants to know if there is a way to arrange the cards while satisfying all the N conditions below.
To help him, determine whether such a way exists. If the answer is yes, also find the lexicographically smallest such arrangement.

To the immediate right of Card 1 (if any) is NOT Card a_1.

To the immediate right of Card 2 (if any) is NOT Card a_2.

\vdots

To the immediate right of Card N (if any) is NOT Card a_N.

Constraints

2 \leq N \leq 10^{5}

1 \leq a_i \leq N

a_i \neq i

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

If no arrangements satisfy the conditions, print -1. If such arrangements exist, print the lexicographically smallest such arrangement, in the following format:

b_1 b_2 \ldots b_N

Here, b_i represents the i-th card from the left.

Sample Input 1

4
2 3 4 1

Sample Output 1

1 3 2 4

The arrangement (1,2,3,4) is lexicographically smaller than (1,3,2,4), but is invalid, since it violates the condition "to the immediate right of Card 1 is not Card 2."

Sample Input 2

2
2 1

Sample Output 2

-1

If no arrangements satisfy the conditions, print -1.

Sample Input 3

13
2 3 4 5 6 7 8 9 10 11 12 13 12

Sample Output 3

1 3 2 4 6 5 7 9 8 10 12 11 13



Sample input:
4
2 3 4 1


Sample output:
1 3 2 4

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
if n==2:
    ans = -1
else:
    from collections import Counter
    c = Counter(a)
    from heapq import heappush as hp, heappop as hpp
    h = []
    
    for i in range(1, n+1):
        hp(h, i)
    ans = [1]
    ban = a[0]
    done = [False]*(n+1)
    done[1] = True
    c[a[0]] -= 1
    for i in range(n-1):
        if len(c)==2 and max(c.values())==sum(c.values())-1:
#             print(c, ans)
            hp(h, ans.pop())
            if c[a[0]]==n-1:
                v0 = a[0]
            else:
                v0 = a[1]
            ans.append(v0)
            while h:
                u = hpp(h)
                if u!=v0:
                    ans.append(u)
            break
        flg = False
#         print(h, done)
        while h:
            num = hpp(h)
#             print(num)
            if num==ban:
                flg = True
            elif done[num]:
                pass
            else:
#                 print("hoge")
                break
        if flg:
            hp(h, ban)
#         print(ban, num, h)
        ans.append(num)
        done[num] = True
        c[a[num-1]] -= 1
        if c[a[i]]==0:
            del c[a[i]]
        ban = a[num-1]
if ans==-1:
    print(ans)
else:
    write(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
if n==2:
    ans = -1
else:
    from collections import Counter
    c = Counter(a)
    from heapq import heappush as hp, heappop as hpp
    h = []
    
    for i in range(1, n+1):
        hp(h, i)
    ans = [1]
    ban = a[0]
    done = [False]*(n+1)
    done[1] = True
    c[a[0]] -= 1
    for i in range(n-1):
        if len(c)==2 and max(c.values())==sum(c.values())-1:
#             print(c, ans)
            ans.pop()
            if c[a[0]]==n-1:
                v0 = a[0]
            else:
                v0 = a[1]
            ans.append(v0)
            while h:
                u = hpp(h)
                if u!=v0:
                    ans.append(u)
            break
        flg = False
#         print(h, done)
        while h:
            num = hpp(h)
#             print(num)
            if num==ban:
                flg = True
            elif done[num]:
                pass
            else:
#                 print("hoge")
                break
        if flg:
            hp(h, ban)
#         print(ban, num, h)
        ans.append(num)
        done[num] = True
        c[a[num-1]] -= 1
        if c[a[i]]==0:
            del c[a[i]]
        ban = a[num-1]
if ans==-1:
    print(ans)
else:
    write(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d
左からおいていくことを考える
残ったカード全てから嫌われている場合、もう置くしかない
貪欲に置いていき、残りカード全てから嫌われてしまったら置く？

そうなるとただの実装難問題だが…

for i in range(N)
    if 残りのカード全てから嫌われてしまっているカードがあったら置く。
    elif 辞書順最小のカードが置けたら置く
    elif 辞書順2番目のカードが存在したら置く。
    else -1?

なのか？？
3枚以上なら絶対置くことが可能そうに見える


残りのカード全てから嫌われてしまっている、判定はどうすればよいと？
嫌われてる辞書(残存するカードのみ)を作っておき、len(辞書) == 2 で、1でない方が嫌われ者

elif 以降はheapqを使うのが良さそう
おいてるフラグ配列を管理しておき、置いてないが出るまでpop
置けない場合は、もう1つ出るまでpopし、置いて最初の奴を戻す

"""

import heapq
import sys

N = int(input())
a = list(map(int,input().split()))

for i in range(N):
    a[i] -= 1

ans = []
dont = None

hq = []
for i in range(N):
    heapq.heappush(hq,i)
    
usable = [True] * N
dic = {}
for i in range(N):
    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1


for loop in range(N):

    flag = True
    
    if len(dic) == 2:
        maxind = None

        for i in dic:
            if maxind == None:
                maxind = i
            elif dic[i] > dic[maxind]:
                maxind = i

        if dic[maxind] == (N-loop-1) and usable[maxind]:
            nc = maxind
            flag = False

    if flag:

        while len(hq) > 0 and (not usable[hq[0]]):
            heapq.heappop(hq)

        if len(hq) == 0:
            print (-1)
            sys.exit()
            
        fi = heapq.heappop(hq)
        if dont != fi:
            nc = fi
        else:

            while len(hq) > 0 and (not usable[hq[0]]):
                heapq.heappop(hq)
            if len(hq) == 0:
                print (-1)
                sys.exit()
            
            sec = heapq.heappop(hq)
            heapq.heappush(hq,fi)
            nc = sec

    #print (nc,a[nc])
    ans.append(nc+1)
    usable[nc] = False
    dic[a[nc]] -= 1
    dont = a[nc]
    if dic[a[nc]] == 0:
        del dic[a[nc]]

print (*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

from collections import Counter

C=Counter(A)

if C.most_common()[0][1]==N:
    print(-1)
    sys.exit()
    
elif C.most_common()[0][1]==N-1:
    x=C.most_common()[0][0]

    if A[x-1]!=x:
        print(-1)
        sys.exit()

A=[0]+A

NOUSE=list(range(N,0,-1))


from itertools import permutations

ANS=[0]
ind=0

while len(NOUSE)>3:
    if NOUSE[-1]==A[ANS[-1]]:
        x=NOUSE.pop()
        y=NOUSE.pop()
        ANS.append(y)
        NOUSE.append(x)
    else:
        x=NOUSE.pop()
        ANS.append(x)

REST=list(permutations(sorted(NOUSE)))

if len(REST)==2:
    for x,y in REST:
        if A[ANS[-1]]!=x and A[x]!=y:
            ANS.extend([x,y])
            break

else:    
    for x,y,z in REST:
        if A[ANS[-1]]!=x and A[x]!=y and A[y]!=z:
            ANS.extend([x,y,z])
            break

print(*ANS[1:])

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
#貪欲+最後ダメだったら手前に割り込ませる+割り込ませてから再度貪欲
n = int(input())
a = [0]+list(map(int, input().split( )))
set_a = set(a[1:])
if len(set_a) <= 2:
    ans = [min(set_a)]
    for i in range(1,n+1):
        if i != min(set_a):
            ans.append(i)
    flag = True
    for i in range(n-1):
        if ans[i+1] == a[ans[i]]:
            flag = False
            break
    if flag:
        print(*ans)
        exit()
    else:
        ans = [max(set_a)]
        for i in range(1,n+1):
            if i != max(set_a):
                ans.append(i)
        flag = True
        for i in range(n-1):
            if ans[i+1] == a[ans[i]]:
                flag = False
                break
        if flag:
            print(*ans)
            exit()
        else:
            print(-1)
            exit()
import heapq

ans = [1]
h = []
for i in range(2,n+1):
    heapq.heappush(h,i)

while h:
    tmp1 = heapq.heappop(h)
    tmp2 = -1
    if a[ans[-1]] != tmp1:#貪欲
        ans.append(tmp1)
    elif h:#貪欲続き・追加できないカードはa[-1]で禁止されているカードのみ
        tmp2 = heapq.heappop(h)
        ans.append(tmp2)
        heapq.heappush(h,tmp1)
    else:##hがカラ
        ind = n-2
        while a[ans[ind]] ==tmp1:
            if ind == 0:
                print(-1)
                exit()
            ind -= 1
        ans = ans[:ind] + [tmp1] + ans[ind:]
        
    

print(*ans)

Submission status: Wrong Answer

Solution code:
#貪欲+最後ダメだったら手前に割り込ませる+割り込ませてから再度貪欲
n = int(input())
a = [0]+list(map(int, input().split( )))

import heapq

ans = [1]
h = []
for i in range(2,n+1):
    heapq.heappush(h,i)

while h:
    tmp1 = heapq.heappop(h)
    tmp2 = -1
    if a[ans[-1]] != tmp1:#貪欲
        ans.append(tmp1)
    elif h:#貪欲続き・追加できないカードはa[-1]で禁止されているカードのみ
        tmp2 = heapq.heappop(h)
        ans.append(tmp2)
        heapq.heappush(h,tmp1)
    else:##hがカラ
        ind = n-2
        while a[ans[ind]] ==tmp1:
            if ind:
                ind -= 1
            else:
                ans2 = [tmp1]
                ans.sort()
                if a[tmp1] != ans[0]:
                    ans = ans2 + ans
                    print(*ans)
                    exit()
                else:
                    try:
                        ans3 = ans2 + [ans[1],ans[0]]
                    except:
                        print(-1)
                        exit()
                    try:
                        ans3 += ans[2:]
                    except:
                        pass
                        print(ans3)
                        exit()
        ans = ans[:ind] + [tmp1] + ans[ind:]

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

import itertools

for i in range(n):
    A[i] -= 1

ANS = []
if n>4:
    ANS.append(0)
B = [0] * n
# B[0] = 1

if n==2 and A==[1,0]:
    print(-1)
elif n==2:
    print("1 2")
elif n==3:
    N=[0,1,2]
    M = [[N[0],N[1],N[2]],[N[0],N[2],N[1]],[N[1],N[0],N[2]],\
    [N[1],N[2],N[0]],[N[2],N[0],N[1]],[N[2],N[1],N[0]]]

    for i in range(6):
        if (n<=3 or A[ANS[-1]] != M[i][0]) and A[M[i][0]] != M[i][1]\
            and A[M[i][1]] != M[i][2]:
            ANS = M[i]
            break
    AA = [str(i+1) for i in ANS]
    print(" ".join(AA))
else:

    a = 1
    b = 2
    while len(ANS) < n-4:
        if A[ANS[-1]] != a:
            ANS.append(a)

            a = b
        elif A[ANS[-1]] != b:
            ANS.append(b)
        b += 1
    # print([i+1 for i in ANS])

    for i in range(len(ANS)):
        B[ANS[i]] += 1
    N = []
    for i in range(len(B)):
        if B[i] == 0:
            N.append(i)
    N.sort()

    # print(N)
    P = list(itertools.permutations([i for i in range(4)], 4))
    # print(P)

    M = []
    for i in range(len(P)):
        ap = []
        for j in range(4):
            ap.append(N[P[i][j]])
        M.append(ap)
    for i in range(3,-1,-1):
        M.sort(key=lambda x:x[i])

    for i in range(len(M)):
        if (n<=4 or A[ANS[-1]] != M[i][0]) and A[M[i][0]] != M[i][1]\
            and A[M[i][1]] != M[i][2]:
            ANS+=M[i]
            break

    AA = [str(i+1) for i in ANS]

    print(" ".join(AA))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, k):
        if k > self.total:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index


n = I()
A = LI()
if n == 2:
    if A[0] == 2 and A[1] == 1:
        print(-1)
    elif A[0] != 2:
        print(1, 2)
    else:
        print(2, 1)
    exit()


bit  = BIT(n + 1)
for i in range(1, n + 1):
    bit.add(i, 1)


ans = []
pre = -1
for j in range(n - 1):
    x = bit.search(1)
    if x == pre:
        x = bit.search(2)
    bit.add(x, -1)
    ans += [x]
    pre = A[x - 1]

last_x = bit.search(1)
bit.add(last_x, -1)
if A[ans[-1] - 1] != last_x:
    ans += [last_x]
    print(*ans)
    exit()


cnt = 0
for k in range(n - 2, -1, -1):
    if A[ans[k] - 1] == last_x:
        x = ans.pop()
        bit.add(x, 1)
        cnt += 1
    else:
        break


if cnt == 1:
    last3 = []
    for a, b, c in permutations((ans.pop(), x, last_x)):
        if A[a - 1] != b and A[b - 1] != c:
            last3 += [[a, b, c]]
    print(*ans + min(last3))
    exit()


ans += [last_x]
x = bit.search(1)
if x == A[ans[-1] - 1]:
    x = bit.search(2)
bit.add(x, -1)
ans += [x]
for l in range(cnt - 1):
    x = bit.search(1)
    bit.add(x, -1)
    ans += [x]
print(*ans)

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
a=[int(i)-1 for i in input().split()]
if N==2:
    print(-1)
    exit()
q=[]
for i in range(1,N+1):
    heapq.heappush(q,i)
X=[0]
for i in range(N-1):
    i=X[-1]
    t=heapq.heappop(q)
    if t==N:
        print(-1)
        exit()
    if a[i]==t:
        t=heapq.heappop(q)
        if t==N:
            print(-1)
            exit()
        heapq.heappush(q,a[i])
    X.append(t)
print(*[i+1 for i in X])

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def small(remain, ng):
    def check_s(res):
        for i in range(len(res) - 1):
            if res[i + 1] == ng[res[i]]:
                return False
        return True

    for res in permutations(remain):
        if check_s(res): return res
    return [-2]

def main():
    def check(i):
        ngi = ng[i]
        for j in range(n):
            if used[j]: continue
            if ng[j] != ngi:
                return True
        return False

    n = II()
    ng = LI1() + [-1]
    # 頂点iを追加しても、残りの頂点でハミルトンパスが存在するかチェックしながら
    # 残りが4点になるまで小さい順に頂点を選んでいく
    ans = []
    used = [False] * n
    ngi = -1
    for _ in range(n - 4):
        for i in range(n):
            if used[i]: continue
            if i == ngi: continue
            if check(i):
                ans.append(i)
                used[i] = True
                ngi = ng[i]
                break
    # 4点以下の残りについては愚直に探す
    remain = []
    for i in range(n):
        if used[i]: continue
        remain.append(i)
    ans += small(remain, ng)
    ans = [x + 1 for x in ans]
    print(*ans)

main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
import sys
import itertools
N=int(input())
A=[0]+list(map(int,input().split()))
if N==2:
    print(-1)
    sys.exit()
if N==3:
    for u in itertools.permutations(range(1,4)): 
        for i in range(2):
            if A[u[i]]!=u[i+1]:
                continue
            else:
                break
        else:
            print(*u)
            sys.exit()
    else:
        print(-1)
        sys.exit()
ans=[1]
lsls=[i for i in range(2,N+1)]
heapify(lsls)
for i in range(N-2):
    u=heappop(lsls)
    if A[ans[-1]]!=u:
        ans.append(u)
    else:
        ans.append(heappop(lsls))
        heappush(lsls,u)
u=lsls[0]
U=0
if A[ans[-1]]!=u:
    ans.append(u)
else:
    for i in range(N-3,-1,-1):
        if A[ans[i]]!=u:
            if i==N-3:
                if A[u]!=ans[i+1]:
                    ans=ans[:i+1]+[u]+ans[i+1:]
                    break
                else:
                    U=ans[N-3]
            else:
                if A[u]!=ans[i+1]:
                    ans=ans[:i+1]+[u]+ans[i+1:]
                else:
                    ans=ans[:i+1]+[u,ans[i+2],ans[i+1]]+ans[i+3:]
                break 
    else:
        if U!=0:
            ans=[U,u]
            lsls=[]
            for i in range(1,N+1):
                if i!=U and i!=u:
                    lsls.append(i)
            heapify(lsls)
            for i in range(N-3):
                u=heappop(lsls)
                if A[ans[-1]]!=u:
                    ans.append(u)
                else:
                    ans.append(heappop(lsls))
                    heappush(lsls,u)
            u=lsls[0]
            ans.append(u)
        else:
            ans=[u]
            lsls=[i for i in range(1,u)]+[i for i in range(u+1,N+1)]
            heapify(lsls)
            for i in range(N-2):
                u=heappop(lsls)
                if A[ans[-1]]!=u:
                    ans.append(u)
                else:
                    ans.append(heappop(lsls))
                    heappush(lsls,u)
            u=lsls[0]
            ans.append(u)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations
readline = sys.stdin.readline

from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.X[-1])
    
    def count(self, v):
        #v(Bの元)以下の個数を取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        #vをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        # i番目の値を取得
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def gets(self, v):
        #累積和がv以下となる最大のindexを返す
        v1 = v
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.sumtree[s+k] < v:
                s += k
                v -= self.sumtree[s]
            k //= 2
        if s == self.size:
            return self.leng()
        return self.count(self.X[s]) + (v1 - self.countsum(self.X[s]))//self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddの代わりに使う
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        #v(Bの元)以linema下のsumを取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        #i番目までのsumを取得
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)


N = int(readline())

A = list(map(int, readline().split()))
if N <= 8:
    ans = True
    for k in permutations(range(1, N+1)):
        for i in range(N-1):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            break
    else:
        ans = False
    if not ans:
        print(-1)
    else:
        print(*k)
else:
    dim = [0]*(N+1)
    for i in range(N):
        a = A[i]
        dim[a] += 1
    T = PMS(list(range(2, N+1)), list(range(2, N+1)))
    L = [1]
    for i in range(N-7):
        k = T.get(1)
        if A[L[-1]-1] == k:
            k = T.get(2)
        L.append(k)
        T.add(k, -1)
    rem = [T.get(i) for i in range(1, 7)]
    for k in permutations(rem):
        if A[L[-1]-1] == k[0]:
            continue
        for i in range(5):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            ans = L + list(k) 
            break
    else:
        L = L + list(k)
        ok = 0
        ng = N-5
        while abs(ok-ng) > 1:
            med = (ok+ng)//2
            C = Counter()
            for l in L[med:]:
                C[A[l-1]] += 1
            k, v = C.most_common()[0]
            if v == N-med-1 and k in L[med:]:
                ng = med
            else:
                ok = med
        C = Counter()
        for l in L[ng:]:
            C[A[l-1]] += 1
        k, _ = C.most_common()[0]
        L = L[:ng] + [k]
        
        
        
        S = set(range(1, N+1)) 
        for l in L:
            S.remove(l)
        S = list(S)
        T = PMS(S, S)
        LS = len(S)
        for _ in range(LS):
            k = T.get(1)
            if A[L[-1]-1] == k:
                k = T.get(2)
            L.append(k)
            T.add(k, -1)
            
        ans = L
    print(*ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

N = int(input())

a = list(map(int,input().split()))

exi = [True] * N
dic = {}

for i in range(N):
    a[i] -= 1

    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1        
     
ans = []
q = [i for i in range(N)]

for loop in range(N):
    
    if len(dic) == 1:

        pf = False

        for j in dic:
            
            if exi[j]:
                ans.append(j)
                exi[j] = False
                pf = True

        dic = {}

        if pf:
            continue


    put = []

    while True:

        if len(q) == 0:
            print (-1)
            sys.exit()

        now = heapq.heappop(q)

        if len(ans) == 0 or (exi[now] and a[ans[-1]] != now):
            ans.append(now)
            break

        elif exi[now]:
            put.append(now)

    for i in put:
        heapq.heappush(q,i)


for i in range(N):
    ans[i] += 1

print (" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

a = list(map(int,input().split()))

A = []

for i in range(N):
    A.append([a[i],i+1])

flag = True



for loop in range(1):

    for i in range(N-2):

        if A[i][0] == A[i+1][1]:
            t = A[i+2]
            A[i+2] = A[i+1]
            A[i+1] = t

            
    if A[-1][1] == A[-2][0]:

        flag = False

        for j in range(N-1):
            j = N-2-j

            if A[j][0] != A[-1][1]:
                A.insert(j+1,A[-1])
                ins = j+2
                del A[-1]
                flag = True
                break
        if not flag:
            A.insert(0,A[-1])
            ins = 1
            del A[-1]

        put = []
        put2 = []
        for i in range(N):
            if i >= ins:
                put2.append([A[i][1],A[i][0]])
            else:
                put.append(A[i])
        put2.sort()

        anssub = []
        for i in put:
            anssub.append(i)
        for i in put2:
            anssub.append([i[1],i[0]])

        A = anssub


    for i in range(N-1):
        if A[i][0] == A[i+1][1]:
            print (-1)
            sys.exit()

    
        


    ans = []
    for i in range(N):
        ans.append(A[i][1])

    print (" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from itertools import permutations


def solve(n, a_list):
    h = []
    for i in range(1, n + 1):
        heappush(h, i)
    res_list = []
    forbidden_list = []
    forbid = 0
    while len(h) > 0:
        i = heappop(h)
        if i != forbid:
            res_list.append(i)
            forbid = a_list[i - 1]
        elif len(h) > 0:
            j = heappop(h)
            res_list.append(j)
            forbid = a_list[j - 1]
            heappush(h, i)
        else:
            # print(i, res_list)
            while len(res_list) > 0:
                j = res_list[-1]
                if a_list[j - 1] == i:
                    heappush(h, res_list.pop())
                else:
                    forbid = a_list[i - 1]
                    res_list.append(i)
                    forbidden_list.append(i)
                    break
            if len(res_list) == 0:
                # print(i, h)
                forbid = a_list[i - 1]
                res_list.append(i)
                forbidden_list.append(i)

        if len(forbidden_list) >= 2:
            if n == 2:
                return "-1"
            else:
                res_list = res_list[:n - 3]
                abc = [i for i in range(1, n + 1) if i not in res_list]
                for a, b, c in permutations(abc):
                    if len(res_list) > 0:
                        if a == a_list[res_list[-1] - 1]:
                            continue
                    if a_list[a - 1] == b:
                        continue
                    if a_list[b - 1] == c:
                        continue
                    res_list = res_list + [a, b, c]
                    h = []
                    break
                return "aaa"
    return " ".join([str(i) for i in res_list])


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)

    print(res)


def test():
    assert solve(4, [2, 3, 4, 1]) == "1 3 2 4"
    assert solve(2, [2, 1]) == "-1"
    assert solve(13, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 12]) == "1 3 2 4 6 5 7 9 8 10 12 11 13"


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from itertools import permutations


def solve(n, a_list):
    h = []
    for i in range(1, n + 1):
        heappush(h, i)
    res_list = []
    forbidden_list = []
    forbid = 0
    while len(h) > 0:
        i = heappop(h)
        if i != forbid:
            res_list.append(i)
            forbid = a_list[i - 1]
        elif len(h) > 0:
            j = heappop(h)
            res_list.append(j)
            forbid = a_list[j - 1]
            heappush(h, i)
        else:
            # print(i, res_list)
            while len(res_list) > 0:
                j = res_list[-1]
                if a_list[j - 1] == i:
                    heappush(h, res_list.pop())
                else:
                    forbid = a_list[i - 1]
                    res_list.append(i)
                    forbidden_list.append(i)
                    break
            if len(res_list) == 0:
                # print(i, h)
                forbid = a_list[i - 1]
                res_list.append(i)
                forbidden_list.append(i)

        if len(forbidden_list) >= 2:
            if n == 2:
                return "-1"
            else:
                res_list = res_list[:n - 3]
                abc = [i for i in range(1, n + 1) if i not in res_list]
                for a, b, c in permutations(abc):
                    if len(res_list) > 0:
                        if a == a_list[res_list[-1] - 1]:
                            continue
                    if a_list[a - 1] == b:
                        continue
                    if a_list[b - 1] == c:
                        continue
                    res_list = res_list + [a, b, c]
                    h = []
                    break
                print("aaa")
    return " ".join([str(i) for i in res_list])


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)

    print(res)


def test():
    assert solve(4, [2, 3, 4, 1]) == "1 3 2 4"
    assert solve(2, [2, 1]) == "-1"
    assert solve(13, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 12]) == "1 3 2 4 6 5 7 9 8 10 12 11 13"


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
d = dict()
for i in range(1, N + 1):
    d[i] = A[i - 1]

A = list(range(1, N + 1))

def c(i, j):
    k = A[j]
    A[j] = A[i]
    A[i] = k

if N == 2:
    print(-1)
    exit()

for i in range(N - 1):
    if d[A[i]] == A[i + 1]:
        if i == N - 2:
            print(-1)
            exit()
        c(i + 1, i + 2)

for i in A:
    print(i, end=" ")