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: Accepted

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 = -1
        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: Accepted

Solution code:
import sys
from itertools import permutations
n = int(input())
a = [0] + list(map(int, input().split()))
if n == 2:
	print(-1)
	sys.exit()
used = [False for _ in range(n+1)]
hate = dict()
for x in a[1:]:
	if x in hate:
		hate[x] += 1
	else:
		hate[x] = 1
cur = 1
ng = 0
ans = []
while len(ans) < n-3:
	if len(hate) == 2:
		worst = False
		for k, v in hate.items():
			if v == n - len(ans) - 1 and not used[k]:
				worst = k
				break
		if worst:
			ans.append(k)
			used[k] = True
			ng = a[k]
			hate[a[k]] -= 1
			if hate[a[k]] == 0:
				del hate[a[k]]
			continue

	while used[cur]:
		cur += 1

	if cur == ng:
		cur_copy = cur+1
		while used[cur_copy]:
			cur_copy += 1
		ans.append(cur_copy)
		used[cur_copy] = True
		ng = a[cur_copy]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]
	else:
		ans.append(cur)
		used[cur] = True
		ng = a[cur]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]

yet = [i for i in range(1, n+1) if not used[i]]
for p in permutations(yet):
	if p[0] != ng and p[1] != a[p[0]] and p[2] != a[p[1]]:
		ans += list(p)
		break

print(*ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from collections import deque
from heapq import heappop, heappush, heapify
from collections import defaultdict

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return False

if N <= 6:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

in_deg = [0] * (N+10)
for x in A:
    in_deg[x] += 1

q = [(-x, i) for i,x in enumerate(in_deg)] # in_deg最大の人を分かるようにしたい
heapify(q)
se = set(q)

def greedy(rest,A,ng_first):
    B = []
    ng = ng_first
    while len(rest) >= 4:
        x = rest[0]; y = rest[1]
        if ng == x:
            B.append(y)
            rest.popleft()
            rest.popleft()
            rest.appendleft(x)
        else:
            B.append(x)
            rest.popleft()
        ng = A[B[-1]]
    return B

rest = deque(range(N))
B = []
prev = N
n = N
for _ in range(N-4):
    while q[0] not in se:
        heappop(q)
    if -q[0][0] == n - 1:
        v = q[0][1]
        B.append(v)
        rest.remove(v)
        B += greedy(rest, A, A[B[-1]])
        break
    x = rest[0]; y = rest[1]
    if A[prev] == x:
        B.append(y)
        rest.popleft()
        rest.popleft()
        rest.appendleft(x)
    else:
        B.append(x)
        rest.popleft()
    prev = B[-1]
    v = A[B[-1]]
    se.remove((-in_deg[v],v))
    in_deg[v] -= 1
    se.add((-in_deg[v],v))
    n -= 1
if len(B) < N:
    B += list(solve_small(rest, A, A[B[-1]]))

print(' '.join(str(x+1) for x in B))

Submission status: Runtime Error

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()))

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

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 not usable[hq[0]]:
            heapq.heappop(hq)

        fi = heapq.heappop(hq)
        if dont != fi:
            nc = fi
        else:

            while not usable[hq[0]]:
                heapq.heappop(hq)
            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: Runtime Error

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush
from itertools import permutations
from operator import itemgetter


# ある条件に当てはまらない限り、i番目に置く数字 xi は、
# それまで使ってない中で最も小さい数字か、
# またはその次に小さい数字（x[i-1]の右に最も小さい数字を置けない場合）
#
# ある条件: 以下の条件を満たす、未使用の数 k がある
# 残っているk以外の全ての数字が、kを共通して右側に置けない数として指定している
#   ＝kを先頭に持ってこない限り、kを置ける機会が無い
#
# ただし残りが少なく（3以下）なってくると例外的なものが出てくるため、それ以降は全探索

def fill_remainings(ans, aaa, x, remainings):
    """
    xを先頭にして残りを昇順に追加
    ただしxの次の要素のみ、aaa[x]で禁止されていた場合はその次と入れ替える
    remainingsにはxを含め3要素以上残っていることが前提
    """
    ans.append(x)
    i = len(ans)
    while remainings:
        k = heappop(remainings)
        if k != x:
            ans.append(k)
    if aaa[x] == ans[i]:
        ans[i], ans[i + 1] = ans[i + 1], ans[i]


def solve(n, aaa):
    if n == 2:
        return [-1]

    in_degrees = defaultdict(lambda: 0)
    for i, a in enumerate(aaa, start=1):
        in_degrees[a] += 1
    in_degrees = dict(in_degrees)

    # 少なくとも残り個数がこれ+1になるまでは「ある条件」には当てはまらない
    # ただし減少することはあるため、直前に再チェック必要
    curr_max = max(in_degrees.values())

    remainings = list(range(1, n + 1))

    aaa.insert(0, 0)

    ans = []
    banned = -1
    for i in range(n - 3):
        if curr_max == n - i - 1:
            curr_x, curr_max = max(in_degrees.items(), key=itemgetter(1))
            if curr_max == n - i - 1:
                fill_remainings(ans, aaa, curr_x, remainings)
                return ans
        top = heappop(remainings)
        if top == banned:
            ans.append(heappop(remainings))
            heappush(remainings, top)
        else:
            ans.append(top)
        banned = aaa[ans[-1]]
        # 確定した数字の入り次数を削減
        if in_degrees[banned] == 1:
            del in_degrees[banned]
        else:
            in_degrees[banned] -= 1
        in_degrees.pop(ans[-1], 0)

    remainings.sort()
    for i, j, k in permutations(remainings):
        if i != banned and j != aaa[i] and k != aaa[j]:
            ans += [i, j, k]
            break

    return ans


n, *aaa = map(int, sys.stdin.buffer.read().split())
print(*solve(n, aaa))

Submission status: Runtime Error

Solution code:
N = int(input())
P = [0] + list(map(int,input().split()))

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

    import heapq
    if P.count(P[1])==N-1:
        ans = [P[1]]
        res = list(range(1,P[1])) + list(range(P[1]+1,N+1))
    else:
        ans = [1]
        res = list(range(2,N+1))
    heapq.heapify(res)

    hpop = heapq.heappop
    hpush = heapq.heappush
    while len(res)>3:
        i = hpop(res)
        if P[ans[-1]] == i:
            j = hpop(res)
            hpush(res,i)
            i = j
        ans.append(i)

    import itertools
    res.sort()
    for q in itertools.permutations(res):
        if P[ans[-1]]!=q[0] and P[q[0]]!=q[1] and P[q[1]]!=q[2]:
            ans.append(q[0])
            ans.append(q[1])
            ans.append(q[2])
            break
    print(*ans)

Submission status: Runtime Error

Solution code:
N = int(input())
P = [0] + list(map(int,input().split()))

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

    import heapq
    ans = [1]
    res = list(range(2,N+1))
    heapq.heapify(res)

    hpop = heapq.heappop
    hpush = heapq.heappush
    while len(res)>3:
        i = hpop(res)
        if P[ans[-1]] == i:
            j = hpop(res)
            hpush(res,i)
            i = j
        ans.append(i)

    import itertools
    res.sort()
    for q in itertools.permutations(res):
        if P[ans[-1]]!=q[0] and P[q[0]]!=q[1] and P[q[1]]!=q[2]:
            ans.append(q[0])
            ans.append(q[1])
            ans.append(q[2])
            break
    print(*ans)

Submission status: Runtime Error

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[-1], ans[-2], last_x):
        if A[a - 1] != b and A[b - 1] != c:
            last3 += [[a, b, c]]
    ans.pop()
    ans.pop()
    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: Runtime Error

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)
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[-1], ans[-2], last_x):
        if A[a - 1] != b and A[b - 1] != c:
            last3 += [[a, b, c]]
    ans.pop()
    ans.pop()
    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: Runtime Error

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)
if A[ans[-1] - 1] != last_x:
    ans += [last_x]
    print(*ans)
    exit()


cnt = 0
for k in range(n - 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[-1], ans[-2], last_x):
        if A[a - 1] != b and A[b - 1] != c:
            last3 += [[a, b, c]]
    ans.pop()
    ans.pop()
    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: Runtime Error

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)
if A[ans[-1] - 1] != last_x:
    ans += [last_x]
    print(*ans)
    exit()


cnt = 0
for k in range(n - 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[-1], ans[-2], last_x):
        if A[a - 1] != b and A[b - 1] != c:
            last3 += [[a, b, c]]
    ans.pop()
    ans.pop()
    print(*ans + min(last3))
    exit()


ans += [last_x]
bit.add(last_x, -1)
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):
    x = bit.search(1)
    bit.add(x, -1)
    ans += [x]
print(*ans)

Submission status: Runtime Error

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):
    heapq.heappush(q,i)
X=[0]
for i in range(N-1):
    i=X[-1]
    t=heapq.heappop(q)
    if a[i]==t:
        t=heapq.heappop(q)
        heapq.heappush(q,a[i])
    X.append(t)
print(*[i+1 for i in X])

Submission status: Runtime Error

Solution code:
from itertools import permutations
from heapq import *
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)]

# smallで作った数列のチェック
def check_s(res, ngi):
    if res[0] == ngi: return False
    for i in range(len(res) - 1):
        if res[i + 1] == ng[res[i]]:
            return False
    return True

# nが小さいときの全探索用
def small(remain, ngi):
    for res in permutations(remain):
        if check_s(res, ngi): return res
    return [-2]

# 使った数を消しながら最小の数を返す
def delpop():
    while 1:
        i = heappop(hp)
        if not used[i]: return i

# 次の数を選ぶ
def next_i(ngi, cr):
    i = delpop()
    if i == ngi:
        ii = delpop()
        heappush(hp, i)
        i = ii
    ngj = ng[i]
    if used[ngj]: return i
    if indeg[ngj] < cr - 1: return i
    heappush(hp, i)
    return ngj

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

n = II()
ng = LI1()
hp = list(range(n))
heapify(hp)
used = [False] * n
indeg = [0] * n
for k in ng: indeg[k] += 1
main()

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = [0] + list(map(int, input().split()))
if n == 2:
	print(-1)
	sys.exit()
used = [False for _ in range(n+1)]
hate = dict()
for x in a[1:]:
	if x in hate:
		hate[x] += 1
	else:
		hate[x] = 1
cur = 1
ng = 0
ans = []
while len(ans) < n:
	if len(hate) == 2:
		worst = False
		for k, v in hate.items():
			if v == n - len(ans) - 1 and not used[k]:
				worst = k
				break
		if worst:
			ans.append(k)
			used[k] = True
			ng = a[k]
			hate[a[k]] -= 1
			if hate[a[k]] == 0:
				del hate[a[k]]
			continue

	while used[cur]:
		cur += 1

	if cur == ng:
		cur_copy = cur+1
		while used[cur_copy]:
			cur_copy += 1
		ans.append(cur_copy)
		used[cur_copy] = True
		ng = a[cur_copy]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]
	else:
		ans.append(cur)
		used[cur] = True
		ng = a[cur]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = [0] + list(map(int, input().split()))
if n == 2:
	print(-1)
	sys.exit()
used = [False for _ in range(n+1)]
hate = dict()
for x in a[1:]:
	if x in hate:
		hate[x] += 1
	else:
		hate[x] = 1
cur = 1
ng = 0
ans = []
while len(ans) < n:
	if len(hate) == 2:
		worst = False
		for k, v in hate.items():
			if v == n - len(ans) - 1:
				worst = k
				break
		if worst:
			ans.append(k)
			used[k] = True
			ng = a[k]
			hate[a[k]] -= 1
			if hate[a[k]] == 0:
				del hate[a[k]]
			continue

	while used[cur]:
		cur += 1

	if cur == ng:
		cur_copy = cur+1
		while used[cur_copy]:
			cur_copy += 1
		ans.append(cur_copy)
		used[cur_copy] = True
		ng = a[cur_copy]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]
	else:
		ans.append(cur)
		used[cur] = True
		ng = a[cur]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]

print(*ans)