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

def factorization(n):
    if n == 1:
        return {1}
    temp = n
    ans = set()
    SS = [i for i in S if i*2 < n]
    for i in SS:
        if temp % i == 0:
            ans.add(i)
    if temp != 1:
        ans.add(temp)
    return ans

S=set()
L = [True]*(10**6+1)
L[0] = False
L[1] = False
for i in range(2, 10**6+1):
    if L[i]:
        S.add(i)
        for j in range(i*2, 10**6+1, i):
            L[j] = False


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


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

ct = 0
s = set()
for i in range(N):
    tmp = factorization(A[i])-{1}
    ct += len(tmp)
    s |= tmp
    if ct != len(s):
        break
else:
    print('pairwise coprime')
    exit()


L1 = A
while len(L1) > 1:
    l = len(L1)//2
    tmp = [0]*l
    for i in range(l):
        tmp[i] = egcd(L1[2*i], L1[2*i+1])
    if len(L1) % 2 == 1:
        tmp.append(L1[-1])
    L1 = tmp

if L1[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

INF=10**9+7
D = [INF]*(10**6+1)
L = [True]*(10**6+1)
L[0] = False
L[1] = False
D[1] = 1
for i in range(2, 10**6+1):
    if L[i]:
        D[i] = i
        for j in range(i*2, 10**6+1, i):
            L[j] = False
            D[j] = min(i, D[j])
# print(D[:101])


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


def factorization(n):
    ans = set()
    if n == 1:
        ans.add(1)
        return ans
    while n>1:
        ans.add(D[n])
        n//=D[n]
    return ans


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

s = set(factorization(A[0])-{1})
for i in range(1, N):
    tmp = factorization(A[i])-{1}
    if tmp & s != set():
        break
    s |= tmp
else:
    print('pairwise coprime')
    exit()

L1 = A
while len(L1) > 1:
    l = len(L1)//2
    k = [0]*l
    for i in range(l):
        k[i] = egcd(L1[2*i], L1[2*i+1])
    if len(L1) % 2 == 1:
        k.append(L1[-1])
    L1 = k

if L1[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n = int(input())
a = [input() for i in range(n)]
b = []
for i in range(n):
  if a[i] in b:
    b.remove(a[i])
  else:
    b.append(a[i])
print(len(b))

### FIXED CODE ###

n = int(input())
a = [input() for i in range(n)]
d = {}
ans = 0
for i in a:
  if i in d:
    d[i] += 1
  else:
    d[i] = 1
for i in d.keys():
  if d[i] % 2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])



### FIXED CODE ###

# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

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

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

ans = [0]*(n-k+1)
for i in range(n-k+1):
    ans[i] = sum(a[i:k+i])

for i in range(len(ans)-1):
    if ans[i] < ans[i+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(1,n-k+1):
    if a[k+i-1] > a[i-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(lambda x: int(x)-1, input().split()))
n = a[0]
his = [-1, n]
f = his.append
while True:
    n = a[n]
    if n in his:
        f(n)
        break
    f(n)
idx = his.index(his[-1])
loop = len(his[his.index(his[-1]):-1])
if len(his) > k:
    print(his[k]+1)
else:
    t = (k - idx) % loop
    g = his[idx:-1]
    print(g[t]+1)


### FIXED CODE ###

from sys import stdin

def main():
    n, k = map(int, stdin.readline().rstrip().split())
    a = [int(x)-1 for x in stdin.readline().rstrip().split()]
    n = a[0]
    his = [-1, n]
    f = his.append
    s = set()
    while True:
        n = a[n]
        if n in s:
            f(n)
            break
        f(n)
        s.add(n)
    idx = his.index(his[-1])
    loop = len(his[his.index(his[-1]):-1])
    if len(his) > k:
        print(his[k]+1)
    else:
        t = (k - idx) % loop
        g = his[idx:-1]
        print(g[t]+1)
main()
### BUGGY 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()
w=[[(i1,l1) for l1 in range(n-i1,1,-1)] for i1 in range(n)]
v=[[(i2,l2) for l2 in range(n-i2,1,-1)] for i2 in range(n)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        for i1l1 in w_sub:
            for i2l2 in v_sub:
                i1,l1=i1l1
                i2,l2=i2l2
                if l1*l2<k:
                    continue
                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)


### 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 ###

import sys
N=int(input())

def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  for k in range(N):
    for i in range(N):
      for j in range(N):
        if i<j and i!=k and k!=j and d[i][j]==d[i][k]+d[k][j]:
          #print((i,k),(k,j))
          shortcut_set.add((i,j))
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

mat=[]
for i in range(N):
  mat.append([int(x) for x in input().split()])
#print(mat)

dist=[[float("inf")]*N for i in range(N)]
graph=[[] for _ in range(N)]
for i in range(N):
  for j in range(N):
    if i==j:
      dist[i][i]=0
    else:
      graph[i].append((j,mat[i][j]))
      dist[i][j]=mat[i][j]
#print(graph)
#print(dist)

shortcut_set=set()
dist=warshall_floyd(dist)
#print(dist)

for i in range(N):
  for j in range(N):
    if dist[i][j]!=mat[i][j]:
      print(-1)
      sys.exit(0)
      
answer=0
for i in range(N):
  for j in range(i+1,N):
    if not (i,j) in shortcut_set:
      answer+=dist[i][j]
      
print(answer)

### FIXED CODE ###

import sys
N=int(input())

def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  for k in range(N):
    for i in range(N):
      for j in range(N):
        if i<j and i!=k and k!=j and d[i][j]==d[i][k]+d[k][j]:
          #print((i,k),(k,j))
          shortcut_set.add((i,j))
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

mat=[]
for i in range(N):
  mat.append([int(x) for x in input().split()])
#print(mat)

dist=[[float("inf")]*N for i in range(N)]
graph=[[] for _ in range(N)]
for i in range(N):
  for j in range(N):
    if i==j:
      dist[i][i]=0
    else:
      graph[i].append((j,mat[i][j]))
      dist[i][j]=mat[i][j]
#print(graph)
#print(dist)

shortcut_set=set()
dist=warshall_floyd(dist)
#print(dist)

for i in range(N):
  for j in range(N):
    if dist[i][j]!=mat[i][j]:
      print(-1)
      sys.exit(0)
      
answer=0
for i in range(N):
  for j in range(i+1,N):
    if not (i,j) in shortcut_set:
      answer+=dist[i][j]
      
print(answer)
### BUGGY CODE ###

n = input()
S = input().split()
q = input()
T = input().split()
cnt = 0

for i in range(len(T)):
    if T[i] in S:
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
S = input().split()
q = int(input())
T = input().split()

#print(len(S&T))
#set:???????????????????????????

cnt = 0

for i in range(len(T)):
    left = 0
    right = n
    while left < right:
        mid = (left+right) // 2
        if int(S[mid]) == int(T[i]):
            cnt += 1
            break
        elif int(S[mid]) < int(T[i]):
            left = mid+1
        else:
            right = mid
print(cnt)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    As = [int(input()) for _ in range(m)]
    mod = 1000000007

    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in As:
        dp[1] = 1
    else:
        dp[1] = 0

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

    ans = dp[n] % mod
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    As = set([int(input()) for _ in range(m)])
    mod = 1000000007

    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in As:
        dp[1] = 1

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

    ans = dp[n] % mod
    print(ans)


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

import sys
n, k = map(int, input().split())
H = list(map(int, input().split()))

H = sorted(H, reverse=True)
if k >= n:
  print(0)
  sys.exit()
for i in range(k):    
  H.pop(0)
cnt = 0
for h in H:
  cnt += h
print(cnt)


### FIXED CODE ###

import sys
n, k = map(int, input().split())
H = list(map(int, input().split()))

H = sorted(H)
if k >= n:
  print(0)
  sys.exit()

cnt = 0
for i in range(n-k):
  cnt += H[i]
print(cnt)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    tmpxor = 0
    tmpor = 0
    for a in A[i:]:
        tmpxor ^= a
        tmpor += a
        if tmpxor != tmpor:
            break
        else:
            ans += 1
print(ans)

### FIXED CODE ###

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

result,right,asum=0,0,0
for left in range(n):
    for r in range(right,n):
        if asum&A[right]:
            break
        asum|=A[right]
        right += 1
    asum -= A[left]
    result += right-left
print(result)
### BUGGY CODE ###

n = int(input())
s = input()

r, g, b = [0] * n, [0] * n, [0] * n
for i in range(0, n):
    if i == 0:
        if s[i] == 'R':
            r[i] = 1
        elif s[i] == 'G':
            g[i] = 1        
        elif s[i] == 'B':
            b[i] = 1
    else:
        if s[i] == 'R':
            r[i] = r[i-1] + 1
            g[i] = g[i-1]
            b[i] = b[i-1]
        elif s[i] == 'G':
            r[i] = r[i-1]
            g[i] = g[i-1] + 1
            b[i] = b[i-1]
        elif s[i] == 'B':
            r[i] = r[i-1]
            g[i] = g[i-1]
            b[i] = b[i-1] + 1   

cnt = 0
for i in range(0, n-2):
    for j in range(n-1, i+1, -1):
        if s[i] == 'R' and s[j] == 'G':
            cnt += b[j] - b[i]
            if (i+j) % 2 == 0 and s[(i+j)//2] == 'B':
                cnt -= 1
        elif s[i] == 'G' and s[j] == 'R':
            cnt += b[j] - b[i]
            if (i+j) % 2 == 0 and s[(i+j)//2] == 'B':
                cnt -= 1
        elif s[i] == 'R' and s[j] == 'B':
            cnt += g[j] - g[i]
            if (i+j) % 2 == 0 and s[(i+j)//2] == 'G':
                cnt -= 1
        elif s[i] == 'B' and s[j] == 'R':
            cnt += g[j] - g[i]
            if (i+j) % 2 == 0 and s[(i+j)//2] == 'G':
                cnt -= 1
        elif s[i] == 'G' and s[j] == 'B':
            cnt += r[j] - r[i]
            if (i+j) % 2 == 0 and s[(i+j)//2] == 'R':
                cnt -= 1
        elif s[i] == 'B' and s[j] == 'G':
            cnt += r[j] - r[i]
            if (i+j) % 2 == 0 and s[(i+j)//2] == 'R':
                cnt -= 1
print(cnt)

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    r=[]
    g=[]
    b=[]
    rdict={}
    gdict={}
    bdict={}
    ans=0
    for i in range(n):
        if s[i]=='R':
            r.append(i)
            rdict[2*i]=2*i
        if s[i]=='G':
            g.append(i)
            gdict[2*i]=2*i
        if s[i]=='B':
            b.append(i)
            bdict[2*i]=2*i
    ans=len(r)*len(g)*len(b)
    for i in r:
        for j in g:
            if i+j in bdict:
                ans-=1
    for i in g:
        for j in b:
            if i+j in rdict:
                ans-=1
    for i in b:
        for j in r:
            if i+j in gdict:
                ans-=1
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
queries = []
for _ in range(Q):
  q = list(input().split()) # 文字列のリスト
  queries.append(q)

r_count = 0
for query in queries:
  t = query[0]
  if (t == '1'):
    r_count += 1
  elif (t == '2'):
    f = query[1]
    new_S = ""
    if(f == '1' and (r_count % 2 == 0)):
      new_S = query[2] + S
    elif(f == '1' and (r_count % 2 == 1)):
      new_S = S + query[2]
    elif(f == '2' and (r_count % 2 == 0)):
      new_S = S + query[2]
    elif(f == '2' and (r_count % 2 == 1)):
      new_S = query[2] + S
    S = new_S

if (r_count % 2 == 1):
  for i, s in enumerate(reversed(S)):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
else:
  print(S)


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

r_count = 0
for query in range(Q):
  query = deque(list(input().split()))
  t = query[0]
  if (t == '1'):
    r_count += 1
  elif (t == '2'):
    f = query[1]
    if(f == '1' and (r_count % 2 == 0)):
      S.appendleft(query[2])
    elif(f == '1' and (r_count % 2 == 1)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 0)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 1)):
      S.appendleft(query[2])

if (r_count % 2 == 1):
  for i, s in enumerate(reversed(S)):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
else:
  for i, s in enumerate(S):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
### BUGGY CODE ###

H,N = list(map(int, input().split()))
As = []
Bs = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    As.append(a)
    Bs.append(b)
    
DP =[0]*(H+1)

for i in range(1,H+1):
    dp = []
    for j in range(len(As)):
        
        if i-As[j]>=0:
            dp.append(DP[i-As[j]] + Bs[j])
        else:
            dp.append(Bs[j])
    DP[i] = min(dp)        

print(DP[-1])

### FIXED CODE ###

import numpy as np
 
H,N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)
DP = np.zeros(H+1)

for i in range(1,H+1):
    DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)
    
print(int(DP[-1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

[n,q]=[int(x) for x in input().split()]
ab=[[int(x) for x in input().split()] for _ in range(n-1)]
px=[[int(x) for x in input().split()] for _ in range(q)]

bubungi=[[x] for x in range(1,n+1)]
ab.sort()
for node in ab[::-1]:
    bubungi[node[0]-1]=bubungi[node[0]-1]+bubungi[node[1]-1]

scores=[0,]*n
for q in px:
    for i in bubungi[q[0]-1]:
        scores[i-1]+=q[1]

print(" ".join([str(s) for s in scores]))

### FIXED CODE ###


n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]
 
neigh = {}
 
scores = [0] * n
 
for i in range(q) :
    scores[px[i][0] - 1] += px[i][1]
#print(*scores) 
for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])
#print(neigh)

sortKey = sorted(neigh.keys())
 
for k in sortKey :
    for e in neigh[k]:
        scores[e-1]+=scores[k-1]
 
print(*scores)
### 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=list(q_i[2])+s
        else:
            s.append(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 ###

def main():
	N, M = map(int, input().split())
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	visited = [False]*(3*N)
	visited[S-1] = True
	while queue:
		pos, d = queue[0]
		queue = queue[1:]
		if pos == T-1:
			print(d//3)
			return
		visited[pos] = True
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if visited[next_pos]:
				continue
			queue.append([next_pos, d+next_d])
	print(-1)

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	N, M = map(int, input().split())
	INF = 2*31-1
	to = [[] for _ in range(N)]
	for _ in range(M):
		u, v = map(int, input().split())
		to[u-1].append(v-1)
	dist = [[INF, INF, INF] for _ in range(N)]

	S, T = map(int, input().split())
	queue = []
	for pos in to[S-1]:
		queue.append([pos, 1])
		dist[pos][1] = 1
	while queue:
		pos, l = queue.pop(0)
		next_positions = to[pos]
		for next_pos in next_positions:
			nl = (l+1)%3
			if dist[next_pos][nl] != INF:
				continue
			dist[next_pos][nl] = dist[pos][l]+1
			queue.append([next_pos, nl])
	ans = dist[T-1][0]
	if ans == INF:
		print(-1)
	else:
		print(ans//3)

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

import itertools

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


L=[]
cnt = 0
for i in range(N):
    L.append(i + A[i])
    R = i - A[i]
    if R in L:
        cnt += L.count(R)

print(cnt)


### FIXED CODE ###

from collections import Counter

def CHK():
    N = int(input())
    A = list(map(int,input().split()))
    L=[]
    R=[]
    cnt = 0
    for i in range(N):
        L.append(i + A[i])
    L_Cnt=Counter(L)

    for i in range(N):
        chk = i -A[i]
        cnt += L_Cnt[chk]
    print(cnt)

CHK()
### BUGGY CODE ###

s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*2019
cnt[0]+=1
c=0
for i in range(n):
  c+=s[i]*(10**i)%2019
  cnt[c%2019]+=1
ans=0
for i in cnt:
  if i<=1:
    pass
  else:
    ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*2019
cnt[0]+=1
c=0
for i in range(n):
  c+=s[i]*pow(10,i,2019)%2019
  cnt[c%2019]+=1
ans=0
for i in cnt:
  if i<=1:
    pass
  else:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys

def prime_list(n):
    l = range(2,n+1)
    i = 2
    while i * i <= n: 
        l = filter(lambda x: x == i or x % i != 0, l)
        i = i + 1
    return l

if __name__ == '__main__':
    l = prime_list(999999)
    for line in sys.stdin:
        n = int(line)
        print len([x for x in l if x <= n])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def prime_list(n):
    l = range(2,n+1)
    i = 2
    while i * i <= n: 
        l = filter(lambda x: x == i or x % i != 0, l)
        i = i + 1
    return l

def mark(s, x):
    for i in xrange(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in xrange(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in xrange(0,n) if s[i] and i > 1]

if __name__ == '__main__':
    l = sieve(999999)
    for line in sys.stdin:
        n = int(line)
        print len([x for x in l if x <= n])
### BUGGY CODE ###

import numpy as np
N = int(input())
As = np.array(input().split()).astype(np.int64)

Q = int(input())

for q in range(Q):
  B, C = map(int, input().split())
  As[np.where(As==B)] = C
  print(As.sum())

### FIXED CODE ###

import numpy as np

N = int(input())
lis = np.zeros(10**5)

As = np.array(input().split()).astype(np.int64)
NUM = As.sum()

for n in As:
  lis[n-1] += 1

Q = int(input())
for q in range(Q):
  B, C = map(int, input().split())
  nnn = lis[B-1]
  lis[B-1] = 0
  lis[C-1] += nnn
  NUM = NUM - B*nnn + C*nnn
  print(int(NUM))
### BUGGY CODE ###

N, K = map(int, input().split())
List = [int(x) for x in input().split()]


for i in range(K):
    if not List:
        print('0')
        exit()
    List.remove(max(List))

print(sum(List))


### FIXED CODE ###

N, K = map(int, input().split())
List = [int(x) for x in input().split()]

if K == 0:
    print(sum(List))
    exit()

if N <= K:
    print('0')
    exit()

List.sort(reverse=True)
del List[:K]

print(sum(List))
### BUGGY CODE ###

# input
N = int(input())
As = list(map(int, input().split()))


# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[[None for _ in range(2)] for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ0であれば1通りしかない
  score[i][i][0] = As[i]
  score[i][i][1] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(N):
    # if k == 0:
    #   continue
    j = i + k
    if j >= N:
      # 幅をとりすぎたら中断
      break
    if i == N - 1:
      score[i][j][0] = score[i][j-1][1] + As[j]
      score[i][j][1] = score[i][j-1][0] - As[j]
    else:
      # print(i,j)
      score[i][j][0] = max(score[i+1][j][1] + As[i], score[i][j-1][1] + As[j])
      score[i][j][1] = min(score[i+1][j][0] - As[i], score[i][j-1][0] - As[j])
    # print_list(score)

print(score[0][N-1][0])


### FIXED CODE ###

# input
N = int(input())
As = list(map(int, input().split()))

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[None for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ1であれば1通りしかない
  if oe == 1:
    score[i][i] = As[i]
  else:
    score[i][i] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j] = score[i][j-1] + As[j]
      else:
        score[i][j] = score[i][j-1] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j] = max(score[i+1][j] + As[i], score[i][j-1] + As[j])
      else:
        score[i][j] = min(score[i+1][j] - As[i], score[i][j-1] - As[j])
    # print_list(score)

print(score[0][N-1])