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

N = int(input())
A = list(map(int, input().split()))
# C = [str(i) for j in range(1, N+1) for i in A if i == j]
C = [str(A.index(i)+1) for i in range(1,N+1)]
L = ' '.join(C)
print(L)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# C = [str(i) for j in range(1, N+1) for i in A if i == j]
# index と　value を入れ替える
C = [0]*N
# print(C)
for k in range(N):
    C[A[k]-1] = str(k+1)
    # C[k] = k
# print(C)
# C = [str(A.index(i)+1) for i in range(1,N+1)]
L = ' '.join(C)
print(L)
### BUGGY CODE ###

N = int(input())
S = input()

for l in reversed(range(1,N//2+1)):
    for i in range(N-2*l+1):
        for j in range(i+l,N-l+1):
            if S[i:i+l] == S[j:j+l]:
                print(l)
                exit()

print(0)

### FIXED CODE ###

from itertools import accumulate
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N = int(input())
S = input()

res = 0
for i in range(1,N):
    m = 0
    r = 0
    for a,b in zip(S,S[i:]):
        if a == b:
            r += 1
        else:
            r = 0
        m = max2(m,r)
    m = min2(m,i)
    res = max2(res, m)

print(res)
### BUGGY CODE ###

def solve(a, b):
    b = [65535 ^ bi for bi in b]
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            v += bin(k).count('1')
            for bi in b:
                bi &= k
                vb = v - bin(bi).count('1')
                bi |= ai
                try:
                    ndp[bi] = max(ndp[bi], vb)
                except KeyError:
                    ndp[bi] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

### FIXED CODE ###

bitcount = [bin(i).count('1') for i in range(0x10000)]
def solve(a, b):
    global bitcount
    b = [65535 ^ bi for bi in b]
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            v += bitcount[k]
            for bi in b:
                bi &= k
                vb = v - bitcount[bi]
                bi |= ai
                try:
                    if ndp[bi] < vb:
                        ndp[bi] = vb
                except KeyError:
                    ndp[bi] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

import sys
f = sys.stdin


while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))
### BUGGY CODE ###

s = [""]+list(input())
t = [""]+list(input())
dp = [[0 for x in range(len(s))] for x in range(len(t))]
for y in range(1,len(t)):
    for x in range(1,len(s)):
        if(t[y] == s[x]):
            dp[y][x] = dp[y-1][x-1]+1
        else:
            dp[y][x] = max(dp[y-1][x],dp[y][x-1])
y,x = len(t)-1,len(s)-1
ans = []
while(dp[y][x] > 0):
    if(dp[y][x] == dp[y-1][x]):
        y -= 1
    elif(dp[y][x] == dp[y][x-1]):
        x -= 1
    else:
        ans.append(s[x])
        y -= 1
        x -= 1
ans.reverse()
print("".join(ans))


### FIXED CODE ###

s = [""]+list(input())
t = [""]+list(input())
dp = [[0 for x in range(len(s))] for x in range(len(t))]
for y in range(1,len(t)):
    for x in range(1,len(s)):
        if(t[y] == s[x]):
            dp[y][x] = dp[y-1][x-1]+1
        else:
            dp[y][x] = max(dp[y-1][x],dp[y][x-1])
y,x = len(t)-1,len(s)-1
ans = []
while(dp[y][x] > 0):
    if(dp[y][x] == dp[y-1][x]):
        y -= 1
    elif(dp[y][x] == dp[y][x-1]):
        x -= 1
    else:
        ans.append(s[x])
        y -= 1
        x -= 1
ans.reverse()
print("".join(ans))
### BUGGY CODE ###

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

count=0
for i in b:
    if a.count(i)==i:
        pass
    elif a.count(i)>i:
            count+=1*(a.count(i)-i)
    else:
            count+=1*a.count(i)
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
s = list(map(int,input().split()))
c = Counter(s)
ans = 0
for i,j in c.items():
    ans += j if j<i else j-i
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())

l=[0]*n
w=0
c=0
ac=[]

for i in range(m):
  p,s=map(str,input().split())
  p=int(p)
  if s=='WA':
    l[p-1]+=1
  else:
    if p not in ac:
      c+=1
      w+=l[p-1]
      ac.append(p)

print(c,w)

### FIXED CODE ###

n,m=map(int,input().split())

l=[0]*n
w=0
c=0
ac=set()

for i in range(m):
  p,s=map(str,input().split())
  p=int(p)
  if s=='WA':
    l[p-1]+=1
  else:
    if p not in ac:
      c+=1
      w+=l[p-1]
      ac.add(p)

print(c,w)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    #先頭から二進数を0埋めした
    bit_data = format(a[i], 'b').zfill(leng)
    for j in range(leng):
        if bit_data[j] == '1':
            bit_acc[j] += 1
ans = 0
for i in range(n):
    bit_data = format(a[i], 'b').zfill(leng)
    for j in range(leng):
        if bit_data[j] == '1':
            ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
        else:
            ans += bit_acc[j] * (2 ** (leng - j - 1))
        ans %= mod
print((ans * 500000004) % mod)
    




### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
for i in range(m):
    b,c =map(int,input().split())
    for i in range(b):
        if A[i] >= c:
            break
        else: A[i] = c
    A = sorted(A)

print(sum(A))

### FIXED CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(m)]
bc = sorted(bc,key=lambda x:-x[1])

sub = []
for i in range(m):
   sub += [bc[i][1]] * bc[i][0]
   if len(sub) > n:
       break

A += sub

print(sum(sorted(A,reverse=True)[:n]))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
s = 0

for i in range(N):
    for j in range(i+1,N):
        c = 1
        q1,mod1 = divmod(A[i],2)
        q2,mod2 = divmod(A[j],2)
        g = 1
        while g != 0:
            if mod1 ^ mod2:
                #print(A[i],A[j])
                #print("a")
                s += c
                s = s%(10**9+7)
            g = max(q1,q2)
            q1,mod1 = divmod(q1,2)
            q2,mod2 = divmod(q2,2)
            c*=2

print(s)

### FIXED CODE ###

import numpy as np
from math import ceil,log2
N = int(input())
a = np.array(list(map(int,input().split())),dtype=np.int64)
ans = 0
count = 1
if max(a) == 0:
    x = 1
else:
    x = ceil(log2(max(a)))

for i in range(x):
    b = a%2
    s = np.count_nonzero(b==1)*np.count_nonzero(b==0)*count
    ans +=s
    count *= 2
    a = a//2
    ans %= 10**9+7
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
z = list(range(k+1))
count = 0
for i in range(k+1):
    for j in range(k+1):
        if (s - (i + j)) in z:
            count += 1
print(count)

### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        if s - (i + j) >= 0 and s - (i + j) <= k:
            count += 1
print(count)
### BUGGY CODE ###

K,S = map(int,input().split())

cnt =0
for a in range(K+1):
  for b in range(min(S+1-a,K+1)):
    for c in range(min(S+1-a-b,K+1)):
      if a+b+c == S:
        cnt += 1
        
print(cnt)  

### FIXED CODE ###

K,S = map(int,input().split())

cnt = 0
for a in range(K+1):
  for b in range(K+1):
    if S-a-b>=0 and S-a-b<=K:
      cnt += 1
        
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    s = a[i]
    del a[i]
    b = sorted(a)
    print(b[int(n/2-1)])
    a.insert(i, s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
for i in range(n):
    if a[i] < b[int(n/2)]:
        print(b[int(n/2)])
    else:
        print(b[int(n/2 -1)])
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

maxx = 0
def total(x):
    return int(x*(x+1)/2)

kitai_P = [total(x)/x for x in P]

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(kitai_P[i:i+k]))
print(ans)



### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

maxx = 0
def total(x):
    return int(x*(x+1)/2)

kitai_P = [total(x)/x for x in P]

ans = 0
now = sum(kitai_P[0:k])
for i in range(n-k+1):
    if i >= 1:
        now = now - kitai_P[i-1] + kitai_P[i+k-1]
    ans = max(ans, now)
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect_left(tmp, i)
    if index == 0:
        tmp.insert(0, i)
    else:
        tmp[index-1] = i

print(len(tmp))


### FIXED CODE ###

import bisect
N = int(input())
A = [-int(input()) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect(tmp, i)
    if index == len(tmp):
        tmp.append(i)
    else:
        tmp[index] = i

print(len(tmp))
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

A.sort()

ans = A[K-1] - A[-K]

tmp = 1

a = 1

for i, Ak in enumerate(A[K:]):
    a = a * (tmp+K-1) // tmp
    ans += a * (Ak - A[N-(K+i)-1])
    ans %= MOD
    tmp += 1

print(int(ans))


### FIXED CODE ###

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

mod = 10 ** 9 + 7

f = [i for i in range(N+1)]
for i in range(2, N+1):
    f[i] *= f[i-1]
    f[i] %= mod
f[0] = 1

q = K - 1
fk = pow(f[q], mod - 2, mod)

total = 0

for i in range(N - K + 1):
    p = N - i - 1

    c = (f[p] * fk * pow(f[p-q], mod-2, mod)) % mod
    total += c * (A[-1 - i] - A[i])
    total %= mod

print(total)
### BUGGY CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = [0] + list(map(int, readline().split()))
    A = np.array(A)
    C = np.zeros(N + 1, dtype=np.int32)

    if A[-1] == 1:
        C[-1] == 1

    for j in range(N, 0, -1):
        cnt = np.count_nonzero(C[j::j] == 1)

        if cnt % 2 == 0:
            if A[j] == 0:
                C[j] = 0
            else:
                C[j] = 1
        else:
            if A[j] == 0:
                C[j] = 1
            else:
                C[j] = 0

    ans = np.sum(C)
    print(ans)
    if ans != 0:
        for i, c in enumerate(C):
            if c == 1:
                print(i)


main()


### FIXED CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = [0] + list(map(int, readline().split()))
    A = np.array(A)
    C = np.zeros(N + 1, dtype=np.int32)

    if A[-1] == 1:
        C[-1] == 1

    for j in range(N, 0, -1):
        cnt = np.count_nonzero(C[j::j])
        C[j] = (cnt % 2) ^ A[j]

    ans = np.sum(C)
    print(ans)
    if ans != 0:
        B = np.arange(N + 1)
        li = B[C == 1]
        print(*li, sep='\n')


main()
### BUGGY CODE ###

#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())

for i in range(Q):
    B, C = list(map(int, input().split()))
    CC = A==B
    NC = CC==False
    A = A*(NC) + C*CC
    print(A.sum())

### FIXED CODE ###

#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
L = np.zeros(10**5,int)
for i in range(len(u)):
    L[u[i]-1] = count[i]
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    asum += L[B-1] * (C-B)
    L[C-1] += L[B-1]
    L[B-1] = 0
    print(asum)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=[[0,ch,cw]]
	heapq.heapify(Q)
	S[ch][cw]=0

	#print(Q)

	while Q:
		#print(Q)
		d,x,y=heapq.heappop(Q)

		if S[x][y]<d:
			continue

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]<d:
				S[x][y]=S[x+xx][y+yy]
				heapq.heappush(Q,[S[x+xx][y+yy],x,y])

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]=="#":
				for xxx in range(-2,3):
					for yyy in range(-2,3):
						if S[x+xxx][y+yyy]==".":
							S[x+xxx][y+yyy]=d+1
							heapq.heappush(Q,[d+1,x+xxx,y+yyy])
				break






	#print(S[2:-2])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	S[ch][cw]=0
	Q=deque()
	Q.append([0,ch,cw])


	d1=[(0,1),(0,-1),(-1,0),(1,0)]
	d2=[(i,j) for i in range(-2,3) for j in range(-2,3)]

	while Q:
		#print(Q)
		d,x,y=Q.popleft()

		for xx,yy in d1:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				Q.appendleft([d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				Q.appendleft([d,x+xx,y+yy])

		for xx,yy in d2:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d+1
				Q.append([d+1,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				continue
			elif S[x+xx][y+yy]>d+1:
				S[x+xx][y+yy]=d+1
				Q.appendleft([d+1,x+xx,y+yy])



	#print(S[2:-2])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


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

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        ds.append(d)

    for x, s, t in xst:
        st = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        for i in range(st, fi):
            if ans[i] == -1:
                ans[i] = x

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
for _ in range(q):
    b, c = list(map(int, input().split()))
    a_list.sort()
    index = []
    for i,j in enumerate(a_list):
        if j>b:
            break
        elif j==b:
            a_list[i]=c
    print(sum(a_list))

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
sum_a = sum(a_list)
num_a = [0]*(10**5)
for i in a_list:
    num_a[i-1] += 1
    
q = int(input())
for _ in range(q):
    b, c = list(map(int, input().split()))
    sum_a = sum_a + c * num_a[b-1] - b *num_a[b-1]
    num_a[c-1] += num_a[b-1]
    num_a[b-1] = 0
    print(sum_a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(5000)

readline = sys.stdin.readline

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

# dp[i][j] = 左端がi、右端がjの状態でのX - Yの最高得点
# dp[0][-1] = 0
# 奇数回目の処理では、
# dp[i][j] = max(dp[i-1][j] + A[i],dp[i][j - 1] + A[j])
# 偶数回目の処理では、
# dp[i][j] = min(dp[i - 1][j]) + A[i],dp[i][j - 1] + A[j])

def f(i,j):
  # 左端がi,右端がjのとき、これから取ることが出来る最大値 右端は含まない[i:j)
  if j - i == 1:
    if (N - (j - i)) % 2 == 0:
      return A[i]
    else:
      return -A[i]
  if (N - (j - i)) % 2 == 0:
    # 先手の場合
    return max(f(i + 1,j) + A[i],f(i,j - 1) + A[j - 1])
  else:
    return min(f(i + 1,j) - A[i],f(i,j - 1) - A[j - 1])
  
print(f(0,N))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

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

# dp[i][j] = 元の数列の中の連続する区間i～jに対して、最終局面に行った時のX-Yの最大値

dp = [[0] * (N + 1) for i in range(N + 1)]
  
for length in range(1, N + 1):
  for i in range(N - length + 1):
    j = i + length
    
    if (N - length) % 2 == 0: # 先手番
      dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
      
    else: # 後手番
      dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])

print(dp[0][N])
### BUGGY CODE ###

N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
num = [0,2,5,5,4,5,6,3,7,6]

DP = [0] * (N+1)

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0:
            DP[i] = max(DP[i], DP[i-n]+1)

A.sort(reverse = True)

ans = ""
remain = DP[N]
match = N
while match > 0:
    for i in range(M):
        n = num[A[i]]
        if match - n >= 0 and DP[match - n] == DP[match] - 1:
            ans += str(A[i])
            match -= n
            break
print(ans)

### FIXED CODE ###

import sys

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

num = [0,2,5,5,4,5,6,3,7,6]

A_num = [(num[a], -a) for a in A]
A_num.sort()

min_A = -A_num[0][1]
min_num = A_num[0][0]
keta_max = N//min_num

DP = [-1] * (N+1)
DP[0] = 0

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0 and DP[i-n] != -1:
            DP[i] = max(DP[i], DP[i-n] * 10 + A[j])

print(DP[N])
### BUGGY CODE ###

mod = 10**6 + 3

fac = [0]*mod
fac[0] = 1
for i in range(1, mod):
    fac[i] = fac[i - 1] * i
    fac[i] %= mod

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)/b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def inverse(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

l = raw_input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = raw_input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(x**n)
        continue
    inv_d = inverse(d, mod)
    x_d = (x * inv_d) % mod
    d_n = (d**n) % mod
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1, d_n)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[(x_d + n - 1) % mod]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * inverse(ans2, mod)
    ans %= mod
    ans = ans * d_n
    ans %= mod
    print(ans)

### FIXED CODE ###

mod = 10**6 + 3

fac = [0]*mod
fac[0] = 1
for i in range(1, mod):
    fac[i] = fac[i - 1] * i
    fac[i] %= mod

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)//b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def mod_pow(x, n, mod):
    ret = 1
    while n > 0:
        if n & 1 != 0:
            ret *= x
            ret %= mod
        x *= x
        x %= mod
        n >>= 1
    return ret

l = input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(mod_pow(x, n, mod))
        continue
    inv_d = mod_inv(d, mod)
    x_d = (x * inv_d) % mod
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[x_d + n - 1]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * mod_inv(ans2, mod)
    ans %= mod
    d_n = mod_pow(d, n, mod)
    ans = ans * d_n
    ans %= mod
    print(ans)
### BUGGY CODE ###

N=int(input())
numbers=list(map(int,input().strip().split()))

target_number=1
i=0
while len(numbers)>i+1:
  if(numbers[i]!=target_number):
    numbers.pop(target_number-1)
  elif(numbers[i]==target_number):
    i+=1
    target_number+=1

if(len(numbers)>1):
  print(N-target_number)
  
elif(len(numbers)==1):
  if(numbers[0]==1):
    print(N-1)
  elif(numbers[0]!=1):
    print(-1)

### FIXED CODE ###

N=int(input())
numbers=list(map(int,input().strip().split()))

target_number=1

for i in range(N):
  if(numbers[i]==target_number):
    target_number+=1
  
if(target_number>1):
  print(N-target_number+1)
  
elif(target_number==1):
  if(1 in numbers):
    print(N-1)
  else:
    print(-1)