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

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(x) for x in input().split()]
dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = arr[i]

for l in range(n-2, -1, -1):
    for r in range(l+1, n):
        dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])
print(dp[0][n-1])


### FIXED CODE ###

def deque(n, arr):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]

    for l in range(n-2, -1, -1):
        for r in range(l+1, n):
            L = arr[l] - dp[l+1][r]
            R = arr[r] - dp[l][r-1]
            dp[l][r] = L if L > R else R
    return dp[0][n-1]

n = int(input())
arr = [int(x) for x in input().split()]
print(deque(n, arr))
### BUGGY CODE ###

n = int(input())
L = [int(i) for i in input().split()]
t = set(L)
dn = {}
dc = {}
All = 0
for i in t:
  dn[i] = L.count(i)
  dc[i] = int(dn[i]*(dn[i]-1)/2)
  All += dc[i]
for i in range(n):
  print(All-dc[L[i]] + int((dn[L[i]]-1)*(dn[L[i]]-2)/2))

### FIXED CODE ###

n = int(input())
L = [int(i) for i in input().split()]
t = set(L)
dn = {}
dc = {}
All = 0
for i in t:
  dn[i] = 0
for i in L:
  dn[i] += 1
for i in t:
  dc[i] = int(dn[i]*(dn[i]-1)/2)
  All += dc[i]
for i in range(n):
  print(All-dc[L[i]] + int((dn[L[i]]-1)*(dn[L[i]]-2)/2))
### BUGGY CODE ###

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
AB = sorted(ab, reverse=True, key=lambda x:x[1])
s = []
ans = "IMPOSSIBLE"
for a,b in ab:
    if a == 1: s.append(b)
    else: break
for A, B in AB:
    if B == n:
        if A in s:
            ans = "POSSIBLE"
    else: break
print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
AB = sorted(ab, reverse=True, key=lambda x:x[1])
s = [0] * n
ans = "IMPOSSIBLE"
for a,b in ab:
    if a == 1: s[b-1] = 1
    else: break
for A, B in AB:
    if B == n:
        if s[A-1] == 1:
            ans = "POSSIBLE"
    else: break
print(ans)
### BUGGY CODE ###

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**12
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

def ev(d0, d1, d2, d3):
    if d0 == n:
        return 0
    tp = (d1, d2, d3)
    if tp in memo:
        return memo[tp]
    re = 1
    if d1 > 0:
        re += ev(d0 + 1, d1 - 1, d2, d3) * d1 / n
    if d2 > 0:
        re += ev(d0, d1 + 1, d2 - 1, d3) * d2 / n
    if d3 > 0:
        re += ev(d0, d1, d2 + 1, d3 - 1) * d3 / n
    re *=n / (n - d0)
    memo[tp] = re
    return re


memo = {}
n = int(input())
a = list(map(int, input().split()))
ds = [0, 0, 0, 0]
for i in range(1, 4):
    ic = a.count(i)
    ds[i] = ic
print(ev(0, ds[1], ds[2], ds[3]))


### FIXED CODE ###

import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    cnt_aa = Counter(aa)
    nc3 = cnt_aa[3]
    nc2 = cnt_aa[2]
    nc1 = cnt_aa[1]
    dp = [[[0] * (n + 1) for _ in range(nc3 + nc2 + 1)] for _ in range(nc3 + 1)]
    for c3 in range(nc3 + 1):
        for c2 in range(nc2 + nc3 - c3 + 1):
            if c3 + c2 > n: break
            for c1 in range(n + 1):
                s = c1 + c2 + c3
                if s > n: break
                if c1 > 0: dp[c3][c2][c1] += (dp[c3][c2][c1 - 1] + n / s) * c1 / s
                if c2 > 0: dp[c3][c2][c1] += (dp[c3][c2 - 1][c1 + 1] + n / s) * c2 / s
                if c3 > 0: dp[c3][c2][c1] += (dp[c3 - 1][c2 + 1][c1] + n / s) * c3 / s
    print(dp[nc3][nc2][nc1])

main()
### BUGGY CODE ###

import sys
import math

def check_sekisairyo(k, p_min, w_i):
    p_now = 0
    k_now = 0
    for w in w_i:
        p_now += w
        if p_now > p_min:
            p_now = w
            k_now += 1
        elif p_now == p_min:
            p_now = 0
            k_now += 1
        if k_now == k and p_now != 0:
            return False
    return True

n, k = map(int, input().split())
w_i = [int(input()) for i in range(n)]
p_min = math.floor(sum(w_i) / k)
w_max = max(w_i)
if p_min < w_max:
    p_min = w_max
while not check_sekisairyo(k, p_min, w_i):
    p_min += 1
print(p_min)

### FIXED CODE ###

import sys

def check_sekisairyo(p_min):
    p_now = 0
    k_now = 0
    for w in w_i:
        p_now += w
        if p_now > p_min:
            p_now = w
            k_now += 1
        elif p_now == p_min:
            p_now = 0
            k_now += 1
        if k_now == k and p_now != 0:
            return False
    return True

n, k = map(int, input().split())
w_i = [int(input()) for i in range(n)]
left, right, p_min = max(w_i), sum(w_i), 0
while left < right:
    p_min = (left + right) // 2
    if check_sekisairyo(p_min):
        right = p_min
    else:
        left = p_min = p_min + 1
print(p_min)
### BUGGY CODE ###

n = int(input())
*a, = map(int, input().split())

m = min(a)
while any(map(lambda x: x%m, a)):
    m -= 1

print(m)


### FIXED CODE ###

from functools import reduce
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
print(reduce(gcd, a))
### BUGGY CODE ###

import numpy as sp
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
xy = sp.reshape(sp.array(xy),(n,2))
x = xy[:, 0]
y = xy[:, 1]
Min = sp.inf
for x1 in range(n-1):
    for x2 in range(x1+1, n):
        minx = min(x[x1], x[x2])
        maxx = max(x[x1], x[x2])
        for y1 in range(n-1):
            for y2 in range(y1+1, n):
                count = 0
                for i in range(n):
                    if minx <= x[i] <= maxx and min(y[y1], y[y2]) <= y[i] <= max(y[y1], y[y2]):
                        count += 1
                if count == k:
                    Min = min(Min, abs((x[x1]-x[x2])*(y[y1]-y[y2])))
print(Min)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

n = int(input())
d = [0] * (n+1)

#片方がその数字だと固定されたときに新しく追加される要素数を計算する関数
def count(u):
    top = int(str(u)[0])
    bottom = int(str(u)[-1])
    #先頭と最後が一緒な候補を入れていく。1けたと2けたは処理が例外的なので先に入れる
    c = []
    if bottom == 0:
        return 0
    if top == bottom:
        c.append(top)
    c.append(int(str(bottom)+str(top)))

    for i in range(len(str(u))-2):
        for k in range(10**(i+1)):
            r = str(bottom)
            r += str(k).zfill(i+1)
            r += str(top)
            c.append(int(r))
    cnt = 0
    for cc in c:
        if cc < u:
            cnt += 2
        elif cc == u:
            cnt += 1
    

    return cnt

d[1] = 1
for i in range(2, n+1):
    d[i] = d[i-1] + count(i)

print(d[-1])

### FIXED CODE ###

n = int(input())

c = [[0] * 10 for i in range(10)]

for i in range(1, n+1):
    start = int(str(i)[0])
    stop = int(str(i)[-1])

    c[start][stop] += 1

r = 0
for i in range(10):
    for j in range(10):
        r += c[i][j] * c[j][i]

#iとjがどちらも0の場合は問題設定と合致しないので引く
print(r)
### BUGGY CODE ###

import re
s=input()
s=re.sub("AC|BB|[^ABC][^ABC]|AX|BX|XB|XC","X",s)
s=re.sub("XX*","X",s)
#print(s)
c=0
while "ABC" in s:
    t=re.subn("ABC","BCA",s)
    s=t[0]
    c+=t[1]
    lastA=s.rfind("A")
    topA=s.find("A")
    topC=s.find("C")
    #print(s,lastA)
    #print(s[lastA:(lastA + 3)])
    if not s[lastA:(lastA + 3)] == "ABC":
        s=s[:lastA]
    s=s[topA:]
    
    s=re.sub("AC|BB|[^ABC][^ABC]|AX|BX|XB|XC","X",s)
    s=re.sub("XX*","X",s)
    #print(s)
print(c)

### FIXED CODE ###

s=input()
i=1
new=[s[0]]
while i<len(s):
    if s[i]=="C" and s[i-1] == "B":
        new.pop()
        new.append("K")
    else:
        new.append(s[i])
    i+=1

cnt=0
ans=0
for i in range(len(new)-1,-1,-1):
    if new[i]=="A" and cnt > 0:
        ans+=cnt
    elif new[i]=="K":
        cnt+=1
    else:
        cnt=0
    
print(ans)
### BUGGY CODE ###

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

ans = 1
#左端の文字を全探索
for i in range(0, N):
    #count = 切り替わりを潰しても良い回数
    if S[i] == '0':
        count = 2 * K -1
    else:
        count = 2 * K
#切り替わりを探す
    for j in range(i+1, N):
        if S[j] != S[j-1]: #1つ前と今の位置が違う時、変えて良い回数を1つ減らす
            count -= 1
        if count == 0: #これ以上変えることができない時
            ans = max(ans, j-i+1) #今までの答えとi番目からj番目までの個数=j-i+1の大きい方を答えに記録
            # print ('A', j)
        elif j == N -1 and count > 0: #最後まで探索したが、交換回数が余っている時
            ans = max(ans, j-i+1) #今までの答えとi番目からj番目までの個数=j-i+1の大きい方を答えに記録
            # print ('B')
        
print (ans)


### FIXED CODE ###

#何も考えずに全探索したらO(N^2)で間に合わない

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

#左端の文字は前の文字と変わった直後のみが候補
lst = [0]
for i in range(0, N-1):
    if S[i] != S[i+1]:
        lst += [i+1]

ans = 0
roop = len(lst)
lst = lst + [N]*(N+10**5)
# print (lst)
# print ('roop', roop)
for i in range(roop):
    if S[lst[i]] == '0':
        # print ('A', lst[i+2*K]- lst[i])
        ans = max(ans, lst[i+2*K]- lst[i])
    if S[lst[i]] == '1':
        # print ('B', lst[i+2*K +1]- lst[i])
        ans = max(ans, lst[i+2*K +1]- lst[i])
print (ans)
### BUGGY CODE ###

# Check Examples

#python 3.7.1

n=int(input())
p=input().split()  
p=list(map(int,p))          
cnt=0

p=sorted(p)
for i in range(n-1):
	arc1=p[i:]
	abc1=p[:i]
	
	arc2=p[i+1:]
	abc2=p[:i+1]
	if len(arc1)>len(abc1) and len(arc2)<=len(abc2):
		cnt=p[i+1]-p[i]

print (cnt)



### FIXED CODE ###

# Check Examples

#python 3.7.1

n=int(input())
p=input().split()  
p=list(map(int,p))          
cnt=0

p=sorted(p)

if p[n//2]!=p[(n//2)-1]:
	cnt=p[n//2]-p[(n//2)-1]



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

import itertools
n=int(input())
S=list(input())

number=list(itertools.combinations(S,3))
print(len(set(number)))


### FIXED CODE ###

n=int(input())
S=input()

ans=0
for i in range(10):
  for j in range(10):
    for k in range(10):
      idxi=S.find(str(i))
      if idxi==-1:
        continue
      idxj=S.find(str(j),idxi+1)
      if idxj==-1:
        continue
      idxk=S.find(str(k),idxj+1)
      if idxk==-1:
        continue
      ans+=1
print(ans)
### BUGGY CODE ###


INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
        # 一度も更新されなければ終了
        if not update:
            break
    return dist

def find_negative_loop(n, es):
    dist = [0] * n
    for i in range(n):
        for e in es:
            if dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                if i == n - 1 and e.end == n - 1:
                    return True
    return False

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))



if find_negative_loop(N, es): # cost < 0 の辺で行き来できる場合も負の閉路になる
  print('inf')
else:
  print(-bellman_ford(N, es,0)[N-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    cnt = 0
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
                if cnt == n-1 and e.end == n-1:
                  print('inf')
                  sys.exit()
        cnt += 1
        # 一度も更新されなければ終了
        if not update or cnt == n:
            break
    return dist

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))


print(-bellman_ford(N, es,0)[N-1])
### BUGGY CODE ###

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

N = (int(input())+1)
A = [int(i) for i in input().split()]
max = 0

for i in range(N-1):
  G = 0
  for j in range(N-1):
    if i==j : continue
    if G==0 : G = A[j] ; continue
    else : G = gcd(G,A[j])
  if max<G :max = G

print(max)

### FIXED CODE ###

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
 
N = (int(input()))
A = [int(i) for i in input().split()]

A1 = [0] * (N)
A2 = [0] * (N)
A3 = [0] * (N)
A1[0] = A[0]
A2[N-1] = A[N-1]

for i in range(N):
  if i==0 : continue
  A1[i] = gcd(A1[i-1],A[i])
  A2[N-1-i] = gcd(A2[N-i],A[N-1-i])
  
for i in range(N):
  if i==0 : A3[i] = A2[i+1] ; continue
  if i==N-1 : A3[i] = A1[i-1] ; continue
  A3[i] = gcd(A1[i-1],A2[i+1])

print(max(A3))
### BUGGY CODE ###

MOD=10**9+7
import sys
read=sys.stdin.readline
from fractions import gcd
from collections import deque
def lcm(a,b):
    return(a//gcd(a,b)*b)
def main():
    N=int(input())
    A=list(map(int,read().split()))
    d=deque(A)
    while(len(d)>1):
        a,b=d.popleft(),d.popleft()
        d.append(lcm(a,b))
    g=d[0]
    res=0
    for i in range(N):
        res=(res+g//A[i])%MOD
    print(res)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

MOD=10**9+7
def factorization(n):
    arr=[]
    tmp=n
    for i in range(2,int(n**0.5)+1):
        if(tmp%i==0):
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr.append([i,cnt])
    if(not arr):
        arr.append([1,1])
    if(tmp!=1):
        arr.append([tmp,1])
    return arr
def moddiv(a,m):
    return pow(a,m-2,m)
N=int(input())
A=list(map(int,input().split()))
cnt={}
for i in range(N):
    arr=factorization(A[i])
    for a,b in arr:
        cnt[a]=max(cnt.get(a,0),b)
g=1;res=0
for k,v in cnt.items():
    g=g*(pow(k,v,MOD))%MOD
for i in range(N):
    res=(res+(g*moddiv(A[i],MOD))%MOD)%MOD
print(res)
### BUGGY CODE ###

from collections import deque
S=input()
Q=int(input())
query=[list(map(str,input().split())) for _ in range(Q)]

ans=deque()
for s in S:
  ans.append(s)
for q in query:
  if len(q)==1:
    ans.reverse()
  else:
    _,f,c=q
    if f=='1':
      ans.appendleft(c)
    else:
      ans.append(c)
print(*ans,sep='')

### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
query=[list(map(str,input().split())) for _ in range(Q)]

ans=deque(S)
reverse=False
for i,q in enumerate(query):
  if len(q)==1:
    reverse=not reverse
  else:
    _,f,c=q
    if (f=='2') ^ reverse:
      ans.append(c)
    else:
      ans.appendleft(c)
if reverse:
  print(*reversed(ans),sep='')
else:
  print(*ans,sep='')
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1, n+1):
    p *= i

print(p%1000000007)

### FIXED CODE ###

n = int(input())
p = 1
for i in range(1, n+1):
    p = (p%1000000007) * (i%100000007)

print(p%1000000007)
### BUGGY CODE ###

n,m = map(int,input().split())
xx = [int(input()) for _ in range(m)]

f = [0]*(n+3)
f[0] = 1
endf = 0
for i in range(1,n+1):
    if i in xx:
        endf += 1
        if endf ==2:
            print(0)
            break
        continue
    else :
        if endf == 1:
            endf = 0
            f[i] = f[i-2]
        else :
            endf = 0
            f[i] = f[i-1] + f[i-2]
else:
    print(f[n]%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
mod = 10**9+7
dp = [1]*(n+1)
for i in range(m):
    dp[int(input())] =0

for i in range(2,n+1):
    if dp[i]!=0:
        dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%mod)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    # a.sort()
    # from collections import deque
    import heapq
    from collections import Counter
    heapq.heapify(a)
    ans = []
    cnt = Counter(a)

    for i in range(n):
        if len(a) == 0:
            break

        tmp = heapq.heappop(a)

        tmpary = []
        for j in range(len(a)):
            tmp2 = heapq.heappop(a)
            # print(tmp,tmp2)

            if tmp2 % tmp == 0:
                # print(tmp,tmp2)
                # print(a)
                continue
            else:
                tmpary.append(tmp2)
        heapq.heapify(tmpary)
        a = tmpary
        if cnt[tmp] > 1:
            continue

        ans.append(tmp)
        # print(a)
        # print(tmp)

    print(len(ans))
    # print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

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


### FIXED CODE ###

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

import math

s = input()
K = int(input())

init = sorted(set(list(s)))[:K]
n=0
z=[]
while(n<len(s)):
    x=[]
    for i in range(len(s)-n):
        if s[i] in init:
            x.append(s[i:i+n+1])
    y = sorted(set(x+z))
    z = y[:K]
    n += 1
print(sorted(set(z))[K-1])

### FIXED CODE ###


import math

s = input()
K = int(input())

init = sorted(set(list(s)))[:K]
n=0
z=[]
while(n<len(s)):
    if n > 500: break
    x=[]
    for i in range(len(s)-n):
        if s[i] in init:
            x.append(s[i:i+n+1])
    y = sorted(set(x+z))
    z = y[:K]
    n += 1
print(sorted(set(z))[K-1])
### BUGGY CODE ###

def main():
    from fractions import gcd
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    # n,*a=map(int,open(0).read().split())
    mod=10**9+7
    a.sort()
    b=a[-1]
    for i in a:
        if b%i!=0:
            b=b*i//gcd(b,i)
    ans=0
    print(sum(b//i%mod for i in a)%mod)    
if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
def calc(h,w):
  row=S[h,:]
  col=S[:,w]
  
  count_h=0
  include=False
  for i,r in enumerate(row):
    if i==w:
        include=True
    if r==".":
      count_h+=1
    else:
      if include:
        break
      count_h=0
      
  count_w=0
  include=False
  for i,c in enumerate(col):
    if i==h:
      include=True
    if c==".":
      count_w+=1
    else:
      if include:
        break
      count_w=0
  return count_h+count_w-1


ans=0        
for i in range(H):
  for j in range(W):
    if S[i,j]==".":
      ans=max(ans, calc(i, j))
    
print(ans)

### FIXED CODE ###

import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
S=np.where(S==".",1,0 )

left=np.zeros((H, W))
right=np.zeros((H, W))
top=np.zeros((H, W))
bottom=np.zeros((H, W))

for i in range(W):
  if i==0:
    left[:,i]=S[:,i]
    right[:,-i-1]=S[:,-i-1]
  else:
    left[:,i]=(left[:,i-1]+1)*S[:,i]
    right[:,-i-1]=(right[:,-i]+1)*S[:,-i-1]
    
for i in range(H):
  if i==0:
    top[i,:]=S[i,:]
    bottom[-1-i,:]=S[-i-1,:]
  else:
    top[i,:]=(top[i-1,:]+1)*S[i,:]
    bottom[-1-i,:]=(bottom[-i,:]+1)*S[-i-1,:]
    
ans=left+top+right+bottom-3
    

print(int(ans.max()))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    b = sum(map(lambda x: (x >> i)&1, a))
    c = n - b
    ans += b * c * (1<<i) % mod
print(ans%mod)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
ans = 0
i = 1
for _ in range(60):
    b = 0
    c = 0
    for j in a:
        if j & i != 0:
            b += 1
        else:
            c += 1
    ans += b * c * i % mod
    i *= 2
print(ans%mod)
### BUGGY CODE ###

K = int(input())
nana = 7
kou = 1
if K % 2 == 0:
    print(-1)
else:
    while True:
        if nana % K == 0:
            break
        nana = (nana * 10 + 7) % K
        kou+=1
    print(kou)


### FIXED CODE ###

K = int(input())
nana=7
kou=1
if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    for i in range(1,K):
        if nana % K == 0:
            break
        nana = (nana * 10 + 7) % K
        kou +=1
    print(kou)