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

from collections import deque
INF = -1
H, W = map(int,input().split())
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

q = deque()
for i in range(H):
    line = list(input())
    for j in range(W):
        if line[j] == '#':
            d[i][j] = 0
            q.append([i, j, 0])

ans = 0

while len(q) > 0:
    p = q.popleft()
    ans = max(ans, p[2])
    for i in range(4):
        nx = p[0] + tx[i]
        ny = p[1] + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and d[nx][ny] == INF:
            d[nx][ny] = p[2] + 1
            q.append([nx, ny, p[2]+1])

print(ans)

### FIXED CODE ###

from collections import deque
INF = -1
H, W = map(int,input().split())
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

q = deque()
for i in range(H):
    line = list(input())
    for j in range(W):
        if line[j] == '#':
            d[i][j] = 0
            q.append([i, j, 0])

ans = 0

while len(q) > 0:
    p = q.popleft()
    ans = max(ans, p[2])
    for i in range(4):
        nx = p[0] + tx[i]
        ny = p[1] + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and d[nx][ny] == INF:
            d[nx][ny] = p[2] + 1
            q.append([nx, ny, p[2]+1])

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

import sys
input = sys.stdin.readline

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

def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)

    return ANS%mod

SUM_N=SUM_M=0
for i in range(N):
    SUM_N+=i*(N-i)

for i in range(M):
    SUM_M+=i*(M-i)

#print((SUM_N*(M**2)+SUM_M*(N**2))/Combi2(N*M,2)*Combi2(N*M,K)*K*(K-1)//2%mod)
print((SUM_N*(M**2)+SUM_M*(N**2))*pow(Combi2(N*M,2),mod-2,mod)*Combi2(N*M,K)*K*(K-1)*pow(2,mod-2,mod)%mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)%mod

    return ANS%mod

SUM_N=SUM_M=0
for i in range(N):
    SUM_N+=i*(N-i)

for i in range(M):
    SUM_M+=i*(M-i)

#print((SUM_N*(M**2)+SUM_M*(N**2))/Combi2(N*M,2)*Combi2(N*M,K)*K*(K-1)//2%mod)
print((SUM_N*(M**2)+SUM_M*(N**2))*pow(Combi2(N*M,2),mod-2,mod)*Combi2(N*M,K)*K*(K-1)*pow(2,mod-2,mod)%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
*a, = map(int, input().split())
dp = [[0]*(N+1) for _ in range(N+1)]

'''
for l in range(1, N+1):
    for i in range(N-l+1):
        j = i+l
        if (N-l) % 2 == 0:
            # first
            dp[i][j] = max([dp[i+1][j]+a[i], dp[i][j-1]+a[j-1]])
        else:
            # second
            dp[i][j] = min([dp[i+1][j]-a[i], dp[i][j-1]-a[j-1]])

print(dp[0][N])
'''


def solve(l, r):
    if l >= r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    t = N-(r-l)
    if t % 2 == 0:
        dp[l][r] = max([solve(l+1, r)+a[l], solve(l, r-1)+a[r-1]])
    else:
        dp[l][r] = min([solve(l+1, r)-a[l], solve(l, r-1)-a[r-1]])
    return dp[l][r]


print(solve(0, N))


### FIXED CODE ###

N = int(input())
*a, = map(int, input().split())
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(1, N+1):
    for i in range(N-l+1):
        j = i+l
        if (N-l) % 2 == 0:
            # first
            dp[i][j] = max([dp[i+1][j]+a[i], dp[i][j-1]+a[j-1]])
        else:
            # second
            dp[i][j] = min([dp[i+1][j]-a[i], dp[i][j-1]-a[j-1]])

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

n = int(input().strip())

l = []
for _ in range(n):
    cmd = input()
    if cmd == "deleteFirst":
        l = l[1:]
    elif cmd == "deleteLast":
        l.pop()
    elif cmd.startswith("insert "):
        _, e = cmd.split(" ")
        l.insert(0, e)
    elif cmd.startswith("delete "):
        _, e = cmd.split(" ")
        if e in l:
            l.remove(e)

print(" ".join(l))

### FIXED CODE ###

from collections import deque

q = deque()

n = int(input().strip())

for _ in range(n):
    cmd = input()
    if cmd == "deleteFirst":
        q.popleft()
    elif cmd == "deleteLast":
        q.pop()
    elif cmd.startswith("insert "):
        v = cmd[7:]
        q.appendleft(v)
    elif cmd.startswith("delete "):
        v = cmd[7:]
        try:
            q.remove(v)
        except ValueError:
            pass
print(" ".join(q))
### BUGGY CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
B=[A[0]]
for i in range(1,N):
    B.append(A[i]+B[i-1])
#print(B)

ans=10**20
for x in range(2,N-1):
    #print(x)
    Q=[]
    q1=B[bisect.bisect_left(B,B[x-1]/2)]
    q2=B[x-1]-q1
    q3=B[bisect.bisect_left(B,B[x-1]/2)-1]
    q4=B[x-1]-q3
    if abs(q1-q2)<abs(q3-q4):
        Q.append(q1)
        Q.append(q2)
    else:
        Q.append(q3)
        Q.append(q4)
    q5=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)]-B[x-1]
    q6=B[N-1]-q5-B[x-1]
    q7=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)-1]-B[x-1]
    q8=B[N-1]-q7-B[x-1]
    
    if abs(q5-q6)<abs(q7-q8):
        Q.append(q5)
        Q.append(q6)
    else:
        Q.append(q7)
        Q.append(q8)
    if (max(Q)-min(Q))<ans:
        ans=(max(Q)-min(Q))
    #print(Q)
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
B=[A[0]]
for i in range(1,N):
    B.append(A[i]+B[i-1])
#print(B)

ans=10**20
for x in range(2,N-1):
    #print(x)
    Q=[]
    q1=B[bisect.bisect_left(B,B[x-1]/2)]
    q2=B[x-1]-q1
    q3=B[bisect.bisect_left(B,B[x-1]/2)-1]
    q4=B[x-1]-q3
    if abs(q1-q2)<abs(q3-q4):
        Q.append(q1)
        Q.append(q2)
    else:
        Q.append(q3)
        Q.append(q4)
    q5=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)]-B[x-1]
    q6=B[N-1]-q5-B[x-1]
    q7=B[bisect.bisect_left(B,(B[N-1]+B[x-1])/2)-1]-B[x-1]
    q8=B[N-1]-q7-B[x-1]
    
    if abs(q5-q6)<abs(q7-q8):
        Q.append(q5)
        Q.append(q6)
    else:
        Q.append(q7)
        Q.append(q8)
    if (max(Q)-min(Q))<ans:
        ans=(max(Q)-min(Q))
    #print(Q)
print(ans)
### BUGGY CODE ###

k = int(input())

def gcd_(a, b):
    if a < b:
        a, b = b, a
    while not a % b == 0:
        a, b = b, a % b
    return b

def gcd(a, b, c):
    length = len({a, b, c})
    if length == 1:
        return a
    elif length == 2:
        x, y = {a, b, c}
        return gcd_(x, y)
    else:
        x, y, z = {a, b, c}
        w = gcd_(x, y)
        return gcd_(w, z)

s = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for h in range(1, k + 1):
            p = gcd(i, j, h)
            s += p
            
print(s)

### FIXED CODE ###

k = int(input())

def gcd_(a, b):
    if a < b:
        a, b = b, a
    while not a % b == 0:
        a, b = b, a % b
    return b

s = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        p = gcd_(i, j)
        if p == 1:
            s += k
        else:
            for h in range(1, k + 1):
                s += gcd_(p, h)
            
print(s)
### BUGGY CODE ###

s=list(input())
q=int(input())

for i in range(1,q+1):
    q_i=input().split()
    if q_i==["1"]:
        s=s[::-1]
    else:
        if q_i[1]=="1":
            s=[q_i[2]]+s
        else:
            s=s+[q_i[2]]

s="".join(s)
print(s)

### FIXED CODE ###

from collections import deque

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

re=False
for i in range(1,q+1):
    q_i=input().split()
    if q_i[0]=="1":
        re= not re
    else:
        if q_i[1]=="1" and re==False:
            s.appendleft(q_i[2])
        elif q_i[1]=="2" and re==True:
            s.appendleft(q_i[2])
        else:
            s.append(q_i[2])

s=list(s)

if re==True:
    s=s[::-1]

s="".join(s)
print(s)
### BUGGY CODE ###

from math import gcd
N,M=list(map(int, input().split()))
S=input()
T=input()
g=gcd(N,M)
l=N*M//g
n=l//N
m=l//M
for i in range(l):
  if i%n==0 and i%m==0:
    if S[i//n]!=T[i//m]:
      print(-1)
      exit()
else:
  print(l)

### FIXED CODE ###

from math import gcd
N,M=list(map(int, input().split()))
S=input()
T=input()
g=gcd(N,M)
l=N*M//g
n=l//N
m=l//M
for i in range(0,l,n):
  if i%m==0:
    if S[i//n]!=T[i//m]:
      print(-1)
      exit()
else:
  print(l)
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break

for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")
            break
    if flag == 1:
        break

if flag == 0:
    print("IMPOSSIBLE")


### FIXED CODE ###

import sys

N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    ship[a].append(b)
    ship[b].append(a)

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

k = input()
l = input().split()
A, B = l[0], l[1]

i = 0
while i * k <= B:
  if A<= i*k <= B:
    print('OK')

print('NG')

### FIXED CODE ###

k = int(input())
l = input().split()
A, B = int(l[0]), int(l[1])

i = 0
while i * k <= B:
  if A <= i*k <= B:
    print('OK')
    break
  i += 1
else:
  print('NG')
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,u,v = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    t = 0
    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    hqt = [(0,u)]
    hqa = [(0,v)]
    mt = 0
    while hqt or hqa:
        while hqt and hqt[0][0] == t:
            ti,pi = hpq.heappop(hqt)
            if ta[pi] != -1:
                continue
            for i in way[pi]:
                if ta[i] == -1:
                    tt[i] = ti+1
                    hpq.heappush(hqt,(ti+1,i))
        while hqa and hqa[0][0] == t:
            ti,pi = hpq.heappop(hqa)
            for i in way[pi]:
                if ta[i] == -1:
                    ta[i] = ti+1
                    hpq.heappush(hqa,(ti+1,i))
        t += 1
    ma = 0
    for i in range(1,n+1):
        if tt[i] == -1:
            continue
        if ma < tt[i]+(ta[i]-tt[i])//2:
            ma = tt[i]+(ta[i]-tt[i])//2
    print(ma)


    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,u,v = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    tt[u] = 0
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] <= ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    ma = 0
    for i in range(1,n+1):
        if tt[i] == -1:
            continue
        if ma < tt[i]+max(0,ta[i]-tt[i]-1):
            ma = tt[i]+max(0,ta[i]-tt[i]-1)
    print(ma)


    return

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

import sys
import queue

q = queue.Queue()
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7
S = []
N, A, B, C = map(int,input().split())
ABC = 'ABC'
q = queue.Queue()
cnt = [A,B,C]
h = ''
q.put((cnt,0,h))
for n in range(N):
    s = input()
    s = s.replace('A','0').replace('B','1').replace('C','2')
    s = list(s)
    S.append(s)


i = 0
#print (S)
while(not q.empty()):
    cnt,d,h = q.get()
    
    #print (cnt,d,h)
    if (d > i):
        i+=1
        if (i==len(S)):
            print ('Yes')
            for k in h:
                print (k)
            exit()
    l,r = S[i]
    l  = int(l)
    r  = int(r)
    if (cnt[l] > 0):
        cnt_ = cnt[:]
        cnt_[l]-=1
        cnt_[r]+=1
        q.put((cnt_,d+1,h+ABC[r]))
        # cnt[l]+=1
        # cnt[r]-=1
    if (cnt[r] > 0):
        cnt_ = cnt[:]
        cnt_[r]-=1
        cnt_[l]+=1
        q.put((cnt_,d+1,h+ABC[l]))
        # cnt[r]+=1
        # cnt[l]-=1
print ('No') 

### FIXED CODE ###

import sys
import queue

q = queue.Queue()
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7
S = []
history = []
N, A, B ,C = map(int,input().split())
d = {}
d['A'] = A
d['B'] = B
d['C'] = C

for n in range(N):
    s = input()
    S.append(s)

def select(L,R,x):
    diff = 1
    if L!=x:
        diff *= -1
    d[L] += diff
    d[R] -= diff
    history.append(x)

for n in range(N):
    L, R = S[n]
    if d[L] >= 2:
        select(L,R,R)
    elif d[L] == 0:
        if d[R] == 0:
            print ('No')
            exit()
        else:
            select(L,R,L)
    elif d[L] == 1:
        if d[R] >= 2:
            select(L,R,L)
        elif d[R] == 0:
            select(L,R,R)
        elif d[R] == 1:
            if n!=N-1:
                if L in S[n+1]:
                    select(L,R,L)
                else:
                    select(L,R,R)
            else:
                select(L,R,L) # どちらでもOK
print ('Yes')
for h in history:
    print (h)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline().strip())

# 1を約数に持つ
divisers = [1 for _ in range(N+1)]
divisers[0] = 0
# divisers[1] = 1

exists = set()
for i in range(2, N+1):
    if i in exists:
        continue
    j = 1
    while i * j <= N:
        tmp = i*j
        exists.add(tmp)
        c = 0
        tmp2 = tmp
        while tmp2 % i == 0:
            tmp2 //= i
            c += 1
        # print(tmp, i, c)
        divisers[tmp] *= c + 1
        j += 1
# print(divisers)

ans = 0
for i in range(1, N+1):
    ans += i * divisers[i]

print(ans)

### FIXED CODE ###

import sys

N = int(sys.stdin.readline().strip())

ans = 0
for i in range(1, N+1):
    j = N // i
    ans += j * (j+1) * i // 2

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

import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
cnt=[0]*N
p[0]=1
cnt[0]=1
for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    temp1=p[j-1]
                    temp2=p[i-1]
                else:
                    temp1=p[j-1]
                    temp2=p[i-1]
                p=[temp2 if k==temp1 else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
        rank[a]=rank[b]
    else:
        par[b]=a
        rank[a]+=rank[b]
        rank[b]=rank[a]

    return

def chk(a,b):
    if par[a]==par[b]:
        print('Yes')
    else:
        print('No')

    return

N,M=map(int, input().split())

par=(list(range(N+1)))
rank=[1]*(N+1)

for _ in range(M):
    A,B=map(int, input().split())
    union(A,B)

print(max(rank))
### BUGGY CODE ###

N,K = input().split()
scores = [int(s) for s in input().split()]

N = int(N)
K = int(K)
SCORES = 1
answer = []
for i in range(K-1,N):
    for j in range(i,i-(K),-1):
        SCORES *= scores[j]
        
    answer.append(SCORES)
    SCORES = 1
    
#print(answer)

for l in range(N-K):
    if answer[l] < answer[l+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K = input().split()
scores = [int(s) for s in input().split()]

N = int(N)
K = int(K)

for i in range(K,N):
    if scores[i] <= scores[i-K]:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

def f_lcs(S, T):
    """
    文字列s, tが与えられる。sの部分列かつtの部分列であるような文字列のうち、
    最長のものを1つ求めよ。文字列xの部分列とは、xから0個以上の文字を除いたあと、
    残りの文字を元の順序で連結して得られる文字列のことである。
    """
    # 参考: https://qiita.com/drken/items/03c7db44ccd27820ea0d
    from itertools import product

    # dp[i+1][j+1]: sのi文字目までとtのj文字目まで見たときにできる
    # Longest Common Subsequence (LCS) の長さ
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
    for i, j in product(range(len(S)), range(len(T))):
        # もし s_i = t_j なら、dp[i][j] から作れるLCSに対し、 s_i(t_jも同じ) を
        # 加えることで、それまでより長いLCSを作りうる
        if S[i] == T[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        # dp[i+1][j] に対して、tのj文字目を見てもLCSの長さは不変。
        # なぜなら、もし、sのi文字目とtのj-1文字目が等しいなら、それらを
        # LCSに加えてしまっているのでsのi文字目とtのj文字目とではLCSの候補にできない。
        # つまり、 dp[i+1][j+1]=dp[i+1][j] である。
        # 逆に、等しくないなら、 sのi文字目とtのj文字目から新たなLCSを作りうるが、
        # これは単に dp[i+1][j+1] の値である。結局、配列の2つの要素のうち小さくない方を選べばいい。
        # 同じく、 dp[i][j+1] に対して、sのi文字目を見てもLCSの長さは不変。
        # これらの事実を反映したのが下の式。
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])

    ans = ''
    # DPテーブルから、現時点で見ているノードがどのノードから遷移してきたかを
    # 特定することでLCSの文字列を復元する
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1  # (i-1, j) -> (i, j) と遷移していた
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1  # (i, j-1) -> (i, j) と遷移していた
        else:
            # (i-1, j-1) -> (i, j) と遷移していた
            ans += S[i - 1]  # T[j-1]でも(同じ文字なので)構わない
            i -= 1
            j -= 1
    ans = ans[::-1]  # DPテーブルの末尾から走査する都合上、解が逆さになる
    return ans

S = input()
T = input()
print(f_lcs(S, T))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
S = input()
T = input()

dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        indicator = 1 if S[i - 1] == T[j - 1] else 0
        dp[i][j] = max(dp[i - 1][j - 1] + indicator, dp[i - 1][j], dp[i][j - 1])

ans = ''


def print_lcs(s, t, dp_table, i, j):
    global ans
    if i == 0 or j == 0:
        return
    if S[i - 1] == T[j - 1]:
        print_lcs(s, t, dp, i - 1, j - 1)
        ans += S[i - 1]
    else:
        if dp[i - 1][j] >= dp[i][j - 1]:
            print_lcs(S, T, dp, i - 1, j)
        else:
            print_lcs(S, T, dp, i, j - 1)


print_lcs(S, T, dp, len(S), len(T))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = np.zeros((), dtype='int')

for i in range(m):
    a, b = map(int, input().split())
    ha = h[a-1]
    hb = h[b-1]

    if ha > hb:
        bad_tower = np.append(bad_tower, b)
    elif ha < hb:
        bad_tower = np.append(bad_tower, a)
    elif ha == hb:
        bad_tower = np.append(bad_tower, a)
        bad_tower = np.append(bad_tower, b)

bad_tower = set(bad_tower)

ans = n - len(bad_tower) + 1

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = np.zeros((n), dtype='int')

for i in range(m):
    a, b = map(int, input().split())
    ha = h[a-1]
    hb = h[b-1]

    if ha > hb:
        bad_tower[b-1] = 1
    elif ha < hb:
        bad_tower[a-1] = 1
    elif ha == hb:
        bad_tower[a-1] = 1
        bad_tower[b-1] = 1

ans = n - np.sum(bad_tower)

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

N, M = map(int, input().split())

list = [0 for i in range(N + 1)]

for m in range(M):
    l, r = map(int, input().split())
    for i in range(l,r+1):
        list[i] += 1

count = 0
for i in range(len(list)):
    if list[i] == M:
        count += 1
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
l_max = -1
r_min = N + 1
for m in range(M):
    l, r = map(int, input().split())
    if l > l_max:
        l_max = l
    if r < r_min:
        r_min = r
print(max(r_min - l_max + 1, 0))
### BUGGY CODE ###

import sys, math

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
res = 0

r = []
g = []
b = []
for i, c in enumerate(s):
    if c == "R":
        r.append(i)
    if c == "G":
        g.append(i)
    if c == "B":
        b.append(i)


res = len(r) * len(b) * len(g)

for i in r:
    for j in g:
        for k in b:
            x,y,z = sorted([i,j,k])
            if y-x ==z-y:
                res -= 1
print(res)

### FIXED CODE ###

import sys, math

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
res = 0

r = []
g = []
b = []
for i, c in enumerate(s):
    if c == "R":
        r.append(i)
    if c == "G":
        g.append(i)
    if c == "B":
        b.append(i)


res = len(r) * len(b) * len(g)

def bin_find(tar):
    left = 0
    right = len(b)
    while left < right:
        mid = (left+right) // 2
        if b[mid] < tar:
            left = mid+1
        elif b[mid] > tar:
            right = mid
        else:
            return mid
    return -1

for i in r:
    for j in g:
        diff = i - j
        if diff < 0:
            diff = -diff
        if diff % 2 == 0:
            target = diff // 2 + min(i,j)
            if target < n and s[target] == 'B':
                res -= 1
        target = min(i,j) - diff
        if target >= 0 and s[target] == 'B':
            res -= 1
        target = max(i,j) + diff
        if target < n and s[target] == "B":
            res -= 1

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

from collections import Counter
def divisors(n):
    lst = []; i = 1
    while i ** 2 <= n:
        q, r = divmod(n, i)
        if r == 0:
            lst.append(i)
            if i != q: lst.append(q)
        i += 1
    return lst

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
cnt = Counter(A)
ans = 0
for a in A:
    if cnt[a] > 1: continue
    for i in divisors(a):
        if i == a: continue
        if cnt[i] >= 1: break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
max_A = A[-1]
cnt = Counter(A)
admissible = [True] * (max_A + 1)
checked = [False] * (max_A + 1)
ans = 0
for a in A:
    if not admissible[a] or checked[a]: continue
    ans += 1
    i = 2
    while a * i <= max_A:
        admissible[a * i] = False
        i += 1
    checked[a] = True
    if cnt[a] > 1: ans -= 1
print(ans)