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

import sys
import collections
input = sys.stdin.readline


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N  = int(input())
lst_A = list(map(int, input().split()))
mod = 10**9+7


lcm_lst = {}
lst_c = []
for i in lst_A:
	c = collections.Counter(prime_factorize(i))
	lst_c.append(c)
	for key in c:
		if key in lcm_lst:
			if(lcm_lst[key]<c[key]):
				lcm_lst[key]=c[key]
		else:
			lcm_lst[key]=c[key]

ans = 0
for c in lst_c:
	g = lcm_lst.copy()
	for key in c:
		g[key]=lcm_lst[key] - c[key]
	a = 1
	for key in g:
		a = (a * key**g[key]) % mod
	ans =  (ans + a)% mod
print(ans)

### FIXED CODE ###

import sys,fractions
input = sys.stdin.readline

mod = 10**9+7

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

lcm = 1
for a in lst_a:
    lcm = a*lcm//fractions.gcd(a,lcm)
lcm %= mod
ans = 0
for a in lst_a:
	ans += lcm*pow(a,mod-2,mod)
	ans %= mod

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

import sys
sys.setrecursionlimit(10**5)
m = 100005
visited = [False]*(m*2)
cnt = [0,0]
def dfs(i):
    global cnt
    if visited[i]:
        return
    visited[i] = True
    cnt[i//m] = cnt[i//m] + 1
    for j in to[i]:
        dfs(j)


n = int(input())
to = [[] for i in range(m*2)]
for i in range(n):
    x,y = map(int,input().split())
    y = y+m
    to[x].append(y)
    to[y].append(x)

ans = 0
for i in range(m):
    cnt = [0,0]
    dfs(i)
    ans = ans + cnt[0]*cnt[1]

print(ans-n)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

m = 100010
uf = UnionFind(m*2)
n = int(input())
for i in range(n):
    x,y = map(int,input().split())
    y = y+m
    uf.Unite(x,y)

lx = {}
ly = {}
ans = 0
for i in range(m):
    rx = uf.Find_Root(i)
    lx[rx] = lx.get(rx,0)+1
    ry = uf.Find_Root(i+m)
    ly[ry] = ly.get(ry,0)+1
for i in range(m*2):
    ans += lx.get(i,0)*ly.get(i,0)

print(ans-n)
### BUGGY CODE ###

N,K = map(int,input().split())
arr = []
while True:
    c = abs(N-K)
    arr.append(c)
    a = set(arr)
    if len(arr) > len(a):
        break
    N = c
print(min(arr))

### FIXED CODE ###

N,K = map(int, input().split())
N = N%K
absolute = abs(K-N)
print(absolute if absolute < N else N)
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    # MODを使わない普通のComb
    def choose(n, r):
        res = 1
        fac = 1
        for i in range(r):
            res *= n - i
            fac *= i + 1
        return res // fac

    s = input()

    l = len(s)

    cnt = dict()

    for i in range(l + 1):
        tmp = s[i:]
        if len(tmp) == 0:
            tmp = '0'
        tmp = int(tmp)
        tmp %= 2019
        if tmp in cnt.keys():
            cnt[tmp] += 1
        else:
            cnt[tmp] = 1

    ans = 0
    for v in cnt.values():
        ans += choose(v, 2)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = input()

    cnt = [0 for _ in range(2019)]
    cnt[0] += 1
    dec = 1
    num = 0
    for i in reversed(s):
        num += int(i) * dec
        num %= 2019
        dec *= 10
        dec %= 2019
        cnt[num] += 1

    ans = 0
    for c in cnt:
        ans += c * (c - 1) // 2

    print(ans)


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

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = []
for i in range(n-1):
    if max(a) % 2 == 1:
        b.append([abs(max(a)//2+1-a[i]),a[i]])
    b.append([abs(max(a)//2-a[i]),a[i]])
b.sort()

print(max(a),b[0][1])

### FIXED CODE ###

import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()
ma = max(a)

b = bisect.bisect(a,ma//2)
koho = []
if b-1 >= 0:
    koho.append([abs(ma//2-a[b-1]),a[b-1]])
if b < n-1:
    koho.append([abs(ma//2-a[b]),a[b]])

if ma % 2 == 1:
    b2 = bisect.bisect(a,ma//2+1)
    if b2-1 >= 0:
        koho.append([abs(ma//2+1-a[b2-1]),a[b2-1]])
    if b2 < n-1:
        koho.append([abs(ma//2+1-a[b2]),a[b2]])

koho.sort()
print(ma,koho[0][1])
### BUGGY CODE ###

from sys import stdin
def input():
    return stdin.readline()[:-1]
#おまじない。

n,m=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(m)]
from itertools import combinations
#union-find召喚
par=[-1]*n
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x] #ここ覚えていなかった
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        False
    else:
        if par[x]>par[y]:#sizeの大きいほうがxにしたい
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True
def same(x,y):
    return find(x)==find(y)
def size(x):
    return -par[find(x)]
comb=list(combinations(range(n),2))
ans=[]

for i in range(m):
    count=0
    num=m-i-1
    unite(AB[num][0]-1,AB[num][1]-1)
    for kumiawase in comb:
        if same(kumiawase[0],kumiawase[1]):
            count+=1
    ans.append(count)
ans=list(reversed(ans))
for i in range(len(ans)-1):
    print(ans[0]-ans[i+1])
print(ans[0])

### FIXED CODE ###

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

par = [-1] * (n + 1)


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def size(x):
    X = find(x)
    return -par[X]


def unite(x, y):
    if find(x) == find(y):
        return False
    X = find(x)
    Y = find(y)
    if size(X) < size(Y):
        x, y = y, x
        X = find(x)
        Y = find(y)
    par[X] += par[Y]
    par[Y] = X
    return True


def is_same(x, y):
    return find(x) == find(y)


def calc(a):
    return a * (a - 1) // 2


goukei = calc(n)
ans = [-1] * (m + 1)
ans[-1] = calc(n)
cnt = 0
AB = [list(map(int, input().split())) for _ in range(m)]
for i in range(m - 1, -1, -1):
    a, b = AB[i]
    if is_same(a, b):
        ans[i] = goukei - cnt
    else:
        A = size(a)
        B = size(b)
        cnt += calc(A + B) - calc(A) - calc(B)
        unite(a, b)
        ans[i] = goukei - cnt
print(*ans[1::], sep="\n")
### BUGGY CODE ###

#!/usr/bin/env python3
#EDPC P

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] *= (dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] *= dp[u][0]
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
#EDPC P

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] *= (dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] *= dp[u][0]
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i + 1))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
result = [0] * n
for x in a:
    result[x-1] += 1
for v in result:
    print(v)
### BUGGY CODE ###

import copy
n=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
mod=10**9+7
lcm=[0]*max(a)
for i in range(n):
	for j in range(2,int(a[i]**0.5)+1):
		cnt=0
		while a[i]%j==0:
			a[i]//=j
			cnt+=1
		lcm[j-1]=max(lcm[j-1],cnt)
	if a[i]!=1:
		lcm[a[i]-1]=max(lcm[a[i]-1],1)
an=1
for i in range(len(lcm)):
	an*=pow(i+1,lcm[i],mod)
	an%=mod
ans=0
for i in range(n):
	ans+=an*pow(b[i],mod-2,mod)
	ans%=mod
print(ans)


### FIXED CODE ###

import copy
n=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
mod=10**9+7
lcm=[0]*max(a)
for i in range(n):
	for j in range(2,int(a[i]**0.5)+1):
		cnt=0
		while a[i]%j==0:
			a[i]//=j
			cnt+=1
		lcm[j-1]=max(lcm[j-1],cnt)
	if a[i]!=1:
		lcm[a[i]-1]=max(lcm[a[i]-1],1)
an=1
for i in range(len(lcm)):
	an*=pow(i+1,lcm[i],mod)
	an%=mod
ans=0
for i in range(n):
	ans+=an*pow(b[i],mod-2,mod)
	ans%=mod
print(ans)
### BUGGY CODE ###

def F(n):
    if n < 3:
        return 0
    elif n < 6:
        return 1
    else:
        ans = 1
        for i in range(n-3+1):
            ans += F(i)
        return ans


s = int(input())
print(F(s) % (10 ** 9 + 7))

### FIXED CODE ###

S = int(input())
DP = [0] * (S + 1)
Mod = 10 ** 9 + 7

if S >= 3:
    DP[0] = 1
    DP[1] = 0
    DP[2] = 0
    for TS in range(3,S+1):
        DP[TS] = DP[TS-1] + DP[TS-3]
    print(DP[S] % Mod)
else:
    print(0)
### BUGGY CODE ###

N,W = map(int, input().split())
L = [0]*(W+1)
for i in range (N):
  X,Y = map(int, input().split())
  for j in range (W,X-1,-1):
    L[j] = max(L[j], L[j-X] + Y)
print(max(L))

### FIXED CODE ###

N,W = map(int, input().split())
L = [0]*(W+1)
for i in range (N):
  X,Y = map(int, input().split())
  for j in range (W,X-1,-1):
    L[j] = max(L[j], L[j-X] + Y)
print(max(L))
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    xn = []
    yn = []
    for i in range(n):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        assert c in ["W", "B"]
        if c == "W":
            y += k
        xn.append(x % (2 * k))
        yn.append(y % (2 * k))

    res = 0
    for i in range(2 * k):
        for j in range(2 * k):
            res = max(res, check(xn, yn, i, j, k))

    print(res)

def check(xn, yn, i, j, k):
    n = len(xn)
    res = 0
    for x, y in zip(xn, yn):
        xi = (x - i) % (2 * k)
        yj = (y - j) % (2 * k)
        if (xi >= k and yj >= k) or (xi < k and yj < k):
            res += 1
    return res

main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    xn = []
    yn = []
    for i in range(n):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        assert c in ["W", "B"]
        if c == "W":
            y += k
        xn.append(x % (2 * k))
        yn.append(y % (2 * k))

    kibou = [[0 for x in range(2 * k + 1)] for y in range(2 * k + 1)]
    for i in range(n):
        x = xn[i]
        y = yn[i]
        squares = get_list_squares(x, y, k)
        for x1, y1, x2, y2 in squares:
            kibou[y1][x1] += 1
            kibou[y1][x2] -= 1
            kibou[y2][x1] -= 1
            kibou[y2][x2] += 1

    rui = ruiseki_2d(kibou, k)
    ma = [max(rui[y]) for y in range(2 * k)]
    print(max(ma))

def get_list_squares(x, y, k):
    # (x, y) of lower bottom
    twok = 2 * k
    assert 0 <= x < twok
    assert 0 <= y < twok
    if x >= k:
        x -= k
        y = (y + k) % (twok)
    xp = x + k
    yp = (y + k) % (twok)
    li = []
    if y < yp:
        li.append((x, y, xp, yp))
        li.append((xp, yp, twok, twok))
        if y != 0:
            li.append((xp, 0, twok, y))
        if x != 0:
            li.append((0, yp, x, twok))
        if x != 0 and  y != 0:
            li.append((0, 0, x, y))
    else:
        li.append((x, y, xp, twok))
        li.append((xp, yp, twok, y))
        if x != 0:
            li.append((0, yp, x, y))
        if y != 0:
            li.append((x, 0, xp, yp))
    return li

def ruiseki_2d(kibou, k):
    rui_1d = [[0 for x in range(2 * k)] for y in range(2 * k)]
    for y in range(k * 2):
        rui_1d[y][0] = kibou[y][0]
        for x in range(1, 2 * k):
            rui_1d[y][x] = rui_1d[y][x - 1] + kibou[y][x]

    rui_2d = [[0 for x in range(2 * k)] for y in range(2 * k)]
    for x in range(2 * k):
        rui_2d[0][x] = rui_1d[0][x]
        for y in range(1, 2 * k):
            rui_2d[y][x] = rui_2d[y - 1][x] + rui_1d[y][x]
    return rui_2d

def debug_print(arr, k):
    for y in reversed(range(2 * k)):
        print(arr[y])

main()
### BUGGY CODE ###

def cal(a):
    cal_sum = 0
    for i in range(1, a + 1):
        cal_sum += i
    return (cal_sum / a)


N, K = map(int, input().split())
p = list(map(int, input().split()))
ans_raw = []
index = 0

for i in range(0, N):
    p[i] = cal(p[i])



for i in range(0, N - K + 1):
    ans = 0
    for j in range(i, i + K):
        ans += p[j]
    ans_raw.append(ans)

max_raw = ans_raw[0]

for i in range(0, len(ans_raw)):
    if max_raw < ans_raw[i]:
        index = i
        max_raw = ans_raw[i]

print(max_raw)

### FIXED CODE ###

def cal(a):
 	return ((1 + a) / 2)
 
N, K = map(int, input().split())
p = list(map(int, input().split()))
ans_raw = []
sum_raw = []
sum_cal = 0
 
for i in range(0, N):
    p[i] = cal(p[i])


for i in range(0, N):
	sum_cal += p[i]
	sum_raw.append(sum_cal)

for i in range(0, N - K):
	ans = sum_raw[i + K] - sum_raw[i]
	ans_raw.append(ans)

ans_0 = sum_raw[K - 1]
ans_raw.append(ans_0)

print(max(ans_raw))
### BUGGY CODE ###

n=int(input())
*t,=map(int,input().split())
tot=sum(t)
*v,=map(int,input().split())
lim1=[]
lim2=[(1,0,0),(-1,tot,tot)]
til=0
for t1,t2,v1 in zip([0]+t,t,v):
	lim1.append((til,til+t2,v1))
	lim2.append((-1,til,til+v1))
	lim2.append((1,til+t2,v1-(til+t2)))
	til+=t2
def mi(time):
	ret=float("inf")
	for l,r,lim in lim1:
		if l<=time<=r:
			ret=min(ret,lim)
	for f,tt,y in lim2:
		if f==-1 and time<=tt:
			ret=min(ret,y-time)
		if f==1 and time>=tt:
			ret=min(ret,time+y)
	return ret
print(sum(mi(i/2) for i in range(tot*2+1))/2)

### FIXED CODE ###

def main():
	n = int(input())
	*t, = map(int, input().split())
	tot = sum(t)
	*v, = map(int, input().split())
	lim1 = []
	lim2 = [(1, 0, 0), (-1, tot, tot)]
	til = 0
	for t1, t2, v1 in zip([0] + t, t, v):
		lim1.append((til, til + t2, v1))
		lim2.append((-1, til, til + v1))
		lim2.append((1, til + t2, v1 - (til + t2)))
		til += t2

	def mi(time):
		ret = float("inf")
		for l, r, lim in lim1:
			if l <= time <= r:
				ret = min(ret, lim)
		for f, tt, y in lim2:
			if f == -1 and time <= tt:
				ret = min(ret, y - time)
			if f == 1 and time >= tt:
				ret = min(ret, time + y)
		return ret

	print(sum(mi(i / 2) for i in range(tot * 2 + 1)) / 2)

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

N = int(input())

ans = [0] * (N+1)

for a in range(1, N+1):
    for i in range(1, int(N**0.5)):
        for j in range(1, i+1):
            for k in range(1, j+1):
                tmp = i**2+j**2+k**2+i*j+j*k+k*i
                if tmp == a and (i==j and j==k and k==i):
                    ans[a] += 1
                elif tmp == a and (i != j and j != k and k != i):
                    ans[a] += 6
                elif tmp == a:
                    ans[a] += 3

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

### FIXED CODE ###

N = int(input())

ans = [0] * (N+1)

for i in range(1, 100):
    for j in range(1, 100):
        for k in range(1, 100):
            tmp = i**2+j**2+k**2+i*j+j*k+k*i
            if 1 <= tmp <= N:
                ans[tmp] += 1
for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###

def f():
    import sys
    input=sys.stdin.buffer.readline
    inputs=sys.stdin.buffer.readlines
    sys.setrecursionlimit(10**9)
    n,m=map(int,input().split())
    edges=[[] for i in range(3+3*n)]
    for i in range(m):
        """#weighted->erase_,__,___=map(int,input().split())
        edges[_].append((__,___))
        #undirected->erase#edges[__].append((_,___))
        """
        _,__=map(int,input().split())
        _*=3;__*=3
        edges[_].append(__+1)
        edges[_+1].append(__+2)
        edges[_+2].append(__)

        #undirected->erase#edges[__].append(_)
        """
    """#weighted->erase

    s,T=map(int,input().split())
    from collections import deque
    dq=deque([])
    dq.append((3*s,0))
    T*=3
    seen=set()
    while dq:
        now,c=dq.popleft()
        seen.add(now)
        for t in edges[now]:
            if t==T :print((c+1)//3);exit()
            if t not in seen:
                dq.append((t,c+1))
    print("-1")
if __name__ == "__main__":
    f()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=[0]*(3*n+3)
seen[3*s]=1
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if seen[t]==0:
            dq.append((t,c+1))
            seen[t]=1
print("-1")
### BUGGY CODE ###

import sys
i = 0
ans=[]
n=int(raw_input())
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.insert(0,s[1])
    elif s[0][-3]=='r':
        ans.pop(0)
    elif s[0][-3]=='a':
        ans.pop()
    else:
        for i,j in enumerate(ans):
            if j==s[1]:
                ans.pop(i)
                break
print ' '.join(ans)

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
### BUGGY CODE ###

def search_index(a, count):
    for i in range(len(a)):
        if a[i] == count:
            return i
    raise ValueError

n = int(input())
a = [int(i) for i in input().split()]
count = 1
while a:
    try:
        index = search_index(a, count)
        count += 1
        a = a[index:]
    except ValueError:
        if count == 1:
            ans = -1
        else:
            ans = n - (count - 1)
        a = []
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
count = 0
for i in range(n):
    if a[i] == count + 1:
        count += 1
if count:
    print(n - count)
else:
    print(-1)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(n-2):
    for j in range(i,n-1):
        for k in range(j,n):
            if s[i]==s[j] or s[j]==s[k] or s[k]==s[i]:
                continue
            if j-i == k-j :
                continue
            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
cnt={}
cnt["R"]=0
cnt["G"]=0
cnt["B"]=0
for i in s:
    cnt[i]+=1
ans = cnt["R"] * cnt["G"] * cnt["B"]
for i in range(n-2):
    for gap in range(1,(n-i+1)//2):
        if s[i] != s[i+gap] and s[i+2*gap] != s[i+gap] and s[i+2*gap] != s[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

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


def returnResMod2(i):
    # i+1の倍数の箱のaiの和の剰余を求める
    res = sum([ansList[k] for k in range(N) if (k+1) % (i+1) == 0]) % 2
    return res


ansList = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = (returnResMod2(i)+A[i]) % 2
    ansList[i] = tmp


M = sum(ansList)
print(M)
if M == 0:
    quit()
print(' '.join([str(i+1) for i, a in enumerate(ansList) if a == 1]))

### FIXED CODE ###

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


def returnResMod2(i):
    # i+1の倍数の箱のaiの和の剰余を求める
    res = sum([ansList[(i+1)*(k+1)-1] for k in range(N//(i+1))]) % 2
    return res


ansList = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = (returnResMod2(i)+A[i]) % 2
    ansList[i] = tmp
    

M = sum(ansList)
print(M)
if M == 0:
    quit()
print(' '.join([str(i+1) for i, a in enumerate(ansList) if a == 1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * n

def solve(idx):
    if idx == 0:
        return 0
    if idx == 1:
        return abs(h[0] - h[1])
    if dp[idx] is not None:
        return dp[idx]

    # dp[idx - 1] + abs(h[idx - 1] - h[idx])
    # dp[idx - 2] + abs(h[idx - 2] - h[idx])
    # ...
    # dp[idx - k] + abs(h[idx - k] - h[idx])

    ans = 10**10
    for i in range(1, k+1):
        if idx - i < 0:
            break
        prev = solve(idx - i)
        temp = prev + abs(h[idx - i] - h[idx])
        ans = min(ans, temp)

    dp[idx] = ans
    return ans

print(solve(n-1))

'''
5 3
10 30 40 50 20
'''

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])
### BUGGY CODE ###

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

n = int(raw_input())

count = 0
for i in range(1,n):
    b = i
    g = gcd(n,b)
    if g == 1:
        count += 1
print count

### FIXED CODE ###

def phi(n):
	r = n
	i = 2
	while i*i <= n:
		if n%i==0:
			r -= r/i
			while n%i==0:
				n /= i
		i += 1
	if n>1: r-= r/n
	return r

n = int(raw_input())
print phi(n)