Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    flag = 1
    ctn = 0
    for _ in range(q):
        query = input().split()
        if flag:
            if query[0] == "1":
                flag = 0
                ctn += 1
            else:
                if query[1] == "1":
                    s = query[2] + s
                else:
                    s = s + query[2]
        else:
            if query[0] == "1":
                flag = 1
                ctn += 1
            else:
                if query[1] == "1":
                    s = s + query[2]
                else:
                    s = query[2] + s

    if ctn % 2 == 1:
        print(s[::-1])
    else:
        print(s)

main()

### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if answer > (x2-x1) * (y2-y1) and K <= sum(map(lambda xy: (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2), xy_list)):
                        answer = (x2-x1) * (y2-y1)

    print(answer)


### FIXED CODE ###

import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if answer > (x2-x1) * (y2-y1) and K <= sum(map(lambda xy: (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2), xy_list)):
                        answer = (x2-x1) * (y2-y1)

    print(answer)
### BUGGY CODE ###

def numsum(a) :
    ans = 0
    for i in range(len(a)) :
        ans += (i + 1) * a[i]
    return ans

n = int(input())
l_a = list(map(int, input().split()))
many = []
for i in range(1, 100001) :
    many.append(l_a.count(i))
bef = numsum(many)
q = int(input())
ans = []
for _ in range(q) :
    b, c = map(int, input().split())
    bef += (c - b)*many[b - 1]
    ans.append(bef)
    many[c - 1] += many[b - 1]
    many[b - 1] = 0

for value in ans :
    print(value)


### FIXED CODE ###

import collections

n = int(input())
l_a = list(map(int, input().split()))
col = collections.Counter(l_a)
bef = sum(l_a)
q = int(input())
ans = []
for _ in range(q) :
    b, c = map(int, input().split())
    bef += (c - b)*col[b]
    ans.append(bef)
    col[c] += col[b]
    col[b] = 0

for value in ans :
    print(value)
### BUGGY CODE ###

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

m = 10**5+1
nums = [0]*m
for i in a: nums[i] += 1

for _ in range(q):
  b,c = map(int, input().split())
  nums[c] += nums[b]
  nums[b] = 0
  ans = 0
  for i in range(1,m): ans += i*nums[i]
  print(ans)

### FIXED CODE ###

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

ans = sum(a)
nums = [0]*(10**5+1)
for i in a: nums[i] += 1

for _ in range(q):
  b,c = map(int, input().split())
  if nums[b] > 0:
    ans -= b*nums[b]
    nums[c] += nums[b]
    ans += c*nums[b]
    print(ans)
    nums[b] = 0
  else:
    print(ans)
### BUGGY CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited_black = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append((h,w))

    for h, w in blacks:
        if not visited_black[h][w]:
            visited_white = [[False] * W for _ in range(H)]
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited_black[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if now == '#':
                        if S[nh][nw] == '.' and (not visited_white[nh][nw]):
                            white += 1
                            visited_white[nh][nw] = True
                            Q.append((nh,nw))
                    else:
                        if S[nh][nw] == '#' and (not visited_black[nh][nw]):
                            black += 1
                            visited_black[nh][nw] = True
                            Q.append((nh,nw))
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append((h,w))

    for h, w in blacks:
        if not visited[h][w]:
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited[h][w] = True
            while Q:
                i, j = Q.pop()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if 0 <= nh < H and 0 <= nw < W:
                        if not visited[nh][nw]:
                            if now != S[nh][nw]:
                                visited[nh][nw] = True
                                Q.append((nh,nw))
                                if S[nh][nw] == '.':
                                    white += 1
                                else:
                                    black += 1
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###




import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    P.extend(A)
          
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()



    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        pass
    else:
        print('not coprime')
        return

    for i in A:
        tmp=[]
        for j in sosus:
            if j>i:
                break
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    print('setwise coprime')

resolve()

### FIXED CODE ###


import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    P.extend(A)
          
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()



    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        pass
    else:
        print('not coprime')
        return

    for i in A:
        tmp=[]
        for j in sosus:
            if j>i:
                break
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
            if i in sosus:
                
                tmp.append(i)
                i = 1
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    print('setwise coprime')

resolve()
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))

ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        ans += nums[i] * nums[j]
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
total = sum(nums[1:])
ans = 0
for i in range(n-1):
    ans += nums[i] * total
    total -= nums[i+1]
print(ans%(10**9+7))
### BUGGY CODE ###

N = int(input())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

cnt = 0
for a in range(N):
    for b in range(N):
        for c in range(N):
            if al[a] < bl[b] < cl[c]:
                cnt += 1
print(cnt)

### FIXED CODE ###

import bisect

N = int(input())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))
al.sort()
# print(al)
bl.sort()
# print(bl)
cl.sort()
# print(cl)

cnt = 0
for i in range(N):
    cnt_ab = bisect.bisect_left(al, bl[i])  # bl[b] = 6 idx= 3
    cnt_bc = len(cl) - bisect.bisect(cl, bl[i])  # bl[b] = 6 idx2= 1
    # print(cnt_ab,cnt_bc)
    cnt += cnt_ab * cnt_bc

print(cnt)
### BUGGY CODE ###


import math
N=int(input())
S=[]
def eratos(n):
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(2,int(math.sqrt(n))+1):
        if isprime[i]==True:
            j=i+i
            while j<=n:
                isprime[j] =False
                j=j+i

    for i in range(n+1):
        if isprime[i]==True:
            S.append(i)
    
    return S
    

T=eratos(110000)

for k in range(N):
    count=0
    l,r=map(int,input().split())

    for i in range(l,r+1):
        if i in T:
            if (i+1)//2 in T:
                count+=1
    print(count)

### FIXED CODE ###


import math
N=int(input())
S=[0]*100010
n=110000
count=0
isprime=[True]*(n+1)
isprime[0]=False
isprime[1]=False
for i in range(2,int(math.sqrt(n))+1):
    if isprime[i]==True:
        j=i+i
        while j<=n:
            isprime[j] =False
            j=j+i

for i in range(2,100010):
    if isprime[i]==True:
        if isprime[(i+1)//2]==True:
            count+=1
    
    S[i]=count
        
                
    

    
for k in range(N):
    l,r=map(int,input().split())
    
    print(S[r]-S[l-1])
### BUGGY CODE ###

import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array(([list(map(int,list(input()))) for _ in range(H)])).T
#print(S)

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):#分けるか分けないか
        ans = np.sum(X)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])#切った回数箱を増やす
            M[-1].append(i+1)#後ろの箱に切る場所を入れていく
        #print(M)
        D = np.zeros(len(M))
        #print(D)
        for s in S:
            D[:] += [np.sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                #print("ans",ans)
                D[:] = [np.sum(s[i] for i in m) for m in M]
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0

ans = INF

Q = deque([(0, Si, Sj)])
while Q:
    dist, i, j = Q.popleft()
    if dist > K:
        break

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist > K:
        break

    distance = dist + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "#"
        Q.append((distance, ni, nj))

print(ans)


### FIXED CODE ###

from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)
### BUGGY CODE ###

N,M=map(int, input().split())
p=[]

for x in range(M):
    p.append(input())

f=0
for x in range(1,N+1):
    if "1 %s" % x in p:
        if "%s %s" % (x,N) in p:
            print("POSSIBLE")
        else:
            f=f+1
    else:
        f=f+1
if f==N:
    print("IMPOSSIBLE")


### FIXED CODE ###

N,M=map(int, input().split())
p=[]
for x in range(M):
    p.append(input())
A=[]
B=[]
for x in range(M):
    a,b=map(int,p[x].split())
    A.append(a)
    B.append(b)
    
isl=[]
for x in range(N):
    isl.append(0)
for x in range(M):
    if A[x]==1:
        isl[B[x]]=1
for x in range(M):
    if B[x]==N:
        isl[A[x]]=isl[A[x]]+1

if 2 in isl:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

X = input()

flag = True
while flag:
    flag = False
    i = 0
    while i < len(X):
        if X[i:i+2] == "ST":
            X = X[:i]+X[i+2:]
            flag = True
        else:
            i += 1

print(len(X))

### FIXED CODE ###

X = input()

s, t = 0, 0
for x in X:
    if x == "S":
        s += 1
    else:
        if s == 0:
            t += 1
        else:
            s -= 1

print(s+t)
### BUGGY CODE ###


lis = []

N,M = [int(i) for i in input().split()]
M_ = M
i = 2

while True:
    if M % i == 0:
        M = M // i
        lis.append(i)
    elif M == 1:
        break
    else:
        i += 1
ans = M_

for n in range(2**len(lis)):
    m = bin(n)[-1:1:-1]
    ret = 1
    for l in range(len(m)):
        if int(m[l]):
            ret *= lis[l]
            if  ret >= N:
                break
    if ret >= N and ret <=ans:
        ans = ret

print(M_//ans)


### FIXED CODE ###

import  math
lis = []

N,M = [int(i) for i in input().split()]

for i in range(1,int(math.sqrt(M))):
    if M % i == 0:
        lis.append(i)
        lis.append(M//i)


lis.sort()
i =1
for i in lis:
    if i >= N:
        break

print(M//i )
### BUGGY CODE ###

from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = dp[i-1]|(dp[i-1]<<ls[i-1])
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

### FIXED CODE ###

from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = (dp[i-1]|(dp[i-1]<<ls[i-1]))&((1<<k)-1)
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)
### BUGGY CODE ###

n=int(input())
import math
p=list(map(float,input().split()))
dp=[[0]*(n) for i in range(n+1)]
dp[0][0]=(1-p[0])
for i in range(1,n):
    dp[0][i]=round(dp[0][i-1]*(1-p[i]),10)
# print(dp[0][1],1-p[2],dp[0][1]*(1-p[2]))
for i in range(1,n+1):
    for j in range(i-1,n):
        if j==0:
            temp1=1 
            temp2=0 
        else:
            temp1=dp[i-1][j-1]
            temp2=dp[i][j-1]
        dp[i][j]=temp1*p[j]+temp2*(1-p[j])
        dp[i][j]=round(dp[i][j],10)
ans=0
# print(dp)
for i in range(n//2+1,n+1):
    ans+=dp[i][n-1]
print(ans)
        

### FIXED CODE ###

n=int(input())
import math
p=list(map(float,input().split()))
for i in range(n):
    p[i]=p[i]*100
dp=[[0]*(n) for i in range(n+1)]
dp[0][0]=(100-p[0])/100
for i in range(1,n):
    dp[0][i]=dp[0][i-1]*(100-p[i])/100
# print(dp[0][1],1-p[2],dp[0][1]*(1-p[2]))
for i in range(1,n+1):
    for j in range(i-1,n):
        if j==0:
            temp1=1 
            temp2=0 
        else:
            temp1=dp[i-1][j-1]
            temp2=dp[i][j-1]
        dp[i][j]=temp1*p[j]/100+temp2*(100-p[j])/100
        dp[i][j]=dp[i][j]
ans=0
# print(dp)
for i in range(n//2+1,n+1):
    ans+=dp[i][n-1]
print(ans)
### BUGGY CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[]
while (j<len(x)-1):
  if (x[j]=="A"):
    if (x[j+1]=="C"):
      s.append(1)
      s.append(0)
      j+=1
    else:s.append(0)
  else:s.append(0)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][0]-1:a[i][1]-1]
  print(sum(p))





### FIXED CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[0]
t=0
while (j<N-1):
  if (x[j]=="A") and (x[j+1]=="C"):
    t+=1
    s.append(t)
  else:s.append(t)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][1]-1]-s[a[i][0]-1]
  print(p)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)

for _ in range(m):
    maximum = a.index(max(a))
    a[maximum] = a[maximum] // 2

print(sum(a))


### FIXED CODE ###

from heapq import heappop,heappush,heapify
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_minus = [-x for x in a]
heapify(a_minus)

pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)

for _ in range(m):
    x = pop()
    push(x//2)

print(-sum(a_minus))
### BUGGY CODE ###

from collections import Counter

# print('input >>')

S = input()
S = S[::-1]

mods = [0] * (len(S)+1)
mods[0] = int(S[0]) % 2019

for i in range(len(mods)-1-1):
    mods[i+1] = (int(S[i+1]) * 10 ** (i+1) + mods[i]) % 2019

# print(mods)

ans = 0

counter = Counter(mods)

for n in counter.values():
    if n > 1:
        ans += (n * (n-1)) // 2

# print('-----output-----')

print(ans)

### FIXED CODE ###

from collections import Counter

# print('input >>')

S = input()
S = S[::-1] + '0'

mod = 0
mods = [0] * 2019
mods[0] += 1

i_mod = 1

for i in range(len(S)-1):
    # mods[i+1] = (int(S[i+1]) * 10 ** (i+1) + mods[i]) % 2019
    i_mod %= 2019
    mod = (int(S[i]) * i_mod + mod) % 2019
    # print(mod)
    mods[mod]+=1
    i_mod *= 10

# print(mods)

ans = 0

# counter = Counter(mods)

# for n in counter.values():
#     if n > 1:
#         ans += (n * (n-1)) // 2

# print('-----output-----')

for m in mods:
    if m > 1:
        ans += (m * (m-1)) // 2

print(ans)
### BUGGY CODE ###

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

generate_seq = []


def is_ok(b):
    len_b = len(b)
    if len_b == 1 and b[0] == 1:
        generate_seq.append(1)
        return True

    processing = []
    for idx in range(len_b):
        if b[idx] != idx + 1:
            processing.append(False)
        else:
            b_tmp = b[:]
            del b_tmp[idx]
            tmp = is_ok(b_tmp)
            if tmp:
                generate_seq.append(idx + 1)
                return True
    return False


result = is_ok(b_list)
if result:
    print('\n'.join(list(map(str, generate_seq))))
else:
    print(-1)


### FIXED CODE ###

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

generate_seq = []


def is_ok(b):
    len_b = len(b)
    if len_b == 1 and b[0] == 1:
        generate_seq.append(1)
        return True

    for idx, val in enumerate(b):
        if idx + 1 < val:
            return False

    processing = []
    for idx in range(len_b):
        if b[idx] != idx + 1:
            processing.append(False)
        else:
            b_tmp = b[:]
            del b_tmp[idx]
            tmp = is_ok(b_tmp)
            if tmp:
                generate_seq.append(idx + 1)
                return True
    return False


result = is_ok(b_list)
if result:
    print('\n'.join(list(map(str, generate_seq))))
else:
    print(-1)