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

N = int(input())
a = [int(x) for x in input().split()]

dp = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[i][i] = a[i]

for l in range(1, N):
    for i in range(N-l):
        dp[i][i+l] = max(a[i] - dp[i+1][i+l], a[i+l] - dp[i][i+l-1])

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

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]

dp = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[i][i] = a[i]

for l in range(1, N):
    for i in range(N-l):
        dp[i][i+l] = max(a[i] - dp[i+1][i+l], a[i+l] - dp[i][i+l-1])

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[:,R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = (C[:-1][:,:,None] == C[1:][:,None,:])
np.cumsum(dp_1,out=dp_1,axis=2)

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)
### BUGGY CODE ###

H,K=map(int,input().split())
H=list(map(int,input().split()))
d=sum(H)
c=[]
for i in range(K):
  c.append(max(H))
  H.remove(max(H))
  if H.count(max(H))>=2:
    H.append(max(H))
if d-sum(c)>0:
  print(d-sum(c))
else:
  print(0)
  


### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort()
if N<K:
  print(0)
else:
  print(sum(H[0:len(H)-K]))
### BUGGY CODE ###

n=int(input())
from itertools import groupby
from collections import deque
s=list(input())
gr=groupby(s)
#flg=0:白の状態
flg=0
black=[]
white=[]
for k,v in gr:
    if flg==0 and k=='#':
        flg=1
        black.append(len(list(v)))
    elif flg==1:
        if k=='#':
            black.append(len(list(v)))
        else:
            white.append(len(list(v)))
if len(black)==0 or len(white)==0:
    print(0)
    exit(0)


cnt=sum(white)
white=deque(white)
black=deque(black)
for _ in range(len(white)):
    white.popleft()
    white.append(black.popleft())
    cnt=min(cnt,sum(white))

print(cnt)





### FIXED CODE ###

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

from itertools import groupby

gr=groupby(s)
#flg=0:白の状態
flg=0
black=[]
white=[]
for k,v in gr:
    if flg==0 and k=='#':
        flg=1
        black.append(len(list(v)))
    elif flg==1:
        if k=='#':
            black.append(len(list(v)))
        else:
            white.append(len(list(v)))
if len(black)==0 or len(white)==0:
    print(0)
    exit(0)




cnt=sum(white)
ans=[cnt]
for i in range(len(white)):
    cnt+=(black[i]-white[i])
    ans.append(cnt)

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

s = str(input())
q = int(input())
for _ in range(q):
    query = list(input().split())
    if query[0] == '1':
        s = s[::-1]
    else:
        if query[1] == '1':
            s = query[2] + s
        else:
            s = s + query[2]
print(s)


### FIXED CODE ###

s = str(input())
q = int(input())
cnt = 0
L = []
R = []
for _ in range(q):
    query = list(input().split())
    if query[0] == '1':
        cnt += 1
    else:
        if query[1] == '1':
            if cnt % 2:
                R.append(query[2])
            else:
                L.append(query[2])
        else:
            if cnt % 2:
                L.append(query[2])
            else:
                R.append(query[2])
s = (''.join(L[::-1]) + s + ''.join(R))
if cnt % 2:
    s = s[::-1]
print(s)
### BUGGY CODE ###

from numba import jit
h, n = map(int, input().split())
magic = []
for _ in range(n):
    magic += [list(map(int, input().split()))]
ans = [float('inf')]*(h+1)
ans[-1] = 0

@jit
def num(h, ans):
    for i in range(h, 0, -1):
        if ans[i] == float('inf'):
            continue
        else:
            for j in magic:
                if i-j[0] < 0:
                    if ans[0] > ans[i]+j[1]:
                        ans[0] = ans[i]+j[1]
                elif ans[i-j[0]] > ans[i]+j[1]:
                    ans[i-j[0]] = ans[i]+j[1]
    return ans[0]
print(num(h, ans))




### FIXED CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())
### BUGGY CODE ###

#Coding:Utf-8

N=int(input())
s=[list(input()) for i in range(N)]
total=0
for l in range(N):
    s[l].sort()
for m in range(N):
    total+=s[m+1:N+1].count(s[m])

print(total)

### FIXED CODE ###

#Coding:Utf-8

N=int(input())
s=[list(input()) for i in range(N)]
total=num=0
dic={}
for l in range(N):
    s[l].sort()
    if dic.get(str(s[l]))==None:
        dic[str(s[l])]=0
    else:
        dic[str(s[l])]+=1
        total+=int(dic[str(s[l])])
print(total)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(str(input()))

s_srt = []
for i in range(n):
    s_srt.append(sorted(s[i]))
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if s_srt[i] == s_srt[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(str(input()))

s_srt = []
for i in range(n):
    s_srt.append(''.join(sorted(s[i])))
s_srt.sort()

tmp = [0,]
k = 0
next = False
for i in range(n - 1):
    if s_srt[i] == s_srt[i + 1]:
        tmp[k] += 1
        next = True
    else:
        if next:
            tmp.append(0)
            k += 1
if tmp[-1] == 0:
    tmp.remove(0)

ans = 0
m = len(tmp)
if m != 0:
    for i in range(m):
        ans += int((tmp[i] + 1) * tmp[i] / 2)

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

n, c = map(int, input().split())
xv = [[int(x) for x in input().split()] for _ in range(n)]
n += 1
xv.insert(0, [0, 0])
maxcal = 0

for i in range(n):
    for j in range(n):
        cal = 0
        d = 0
        for k in range(0, i + 1):
            cal += xv[k][1]
        if i != j:
            for k in range(j, n):
                cal += xv[k][1]
            d = xv[i][0] * 2 + (c - xv[j][0])
            d2 = xv[i][0] + (c - xv[j][0]) * 2
            d = min(d, d2)
        else:
            d = xv[i][0]
        if d < c:
            maxcal = max(maxcal, cal - d)
print(maxcal)


### FIXED CODE ###

n, c = map(int, input().split())
xv = [[int(x) for x in input().split()] for _ in range(n)]
xv.insert(0, [0, 0])
n += 1
oa = [0] * (n + 1)
ob = [0] * (n + 1)
maxr = [0] * (n + 1)
maxl = [0] * (n + 1)
for i in range(1, n):
    oa[i] = oa[i - 1] + xv[i][1]
    maxr[i] = max(maxr[i - 1], oa[i] - xv[i][0])
ob[n - 1] = xv[i][1]
for i in range(n - 1, -1, -1):
    ob[i] = xv[i][1] + ob[i + 1]
    maxl[i] = max(maxl[i + 1], ob[i] - (c - xv[i][0]))
cal1 = max(maxr[n-1], maxl[0])
cal2 = 0
cal3 = 0
for i in range(n):
    cal2 = max(cal2, oa[i] - 2 * xv[i][0] + maxl[i+1])
    cal3 = max(cal3, ob[i] - 2 * (c - xv[i][0]) + maxr[i-1])
print(max(cal1, cal2, cal3))
### BUGGY CODE ###

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

A = sorted(A)

seed = []

while A:    
    wareta = set()
    warenai = []

    q = A.pop(0)
    for a in A:
        if a % q == 0:
            wareta.add(a)
        else:
            warenai.append(a)

    if q not in wareta:
        seed.append(q) 

    A = warenai[:]

print(len(seed))

### FIXED CODE ###

from collections import Counter

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

maxA = max(A)
C = Counter(A)

D = {a: 0 for a in A}
for a in A:
  t = 2
  while a * t <= maxA:
      D[a * t] = 1
      t += 1

ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1

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

N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2+1):
  matchfunc=lambda x: (x==b[b[x]-1]-1 and b[x]!=x+1)
  match=list(filter(matchfunc,range(N)))
  #print(match)
  for i in range(len(match)):
    c[match[i]]+=1
    b[match[i]]=a[match[i]][c[match[i]]]
    if match==[]:
      print(-1)
      exit()  
  #for i in range(N):
    #if b[i]==i+1:
      #cnt+=0
    #elif i==b[b[i]-1]-1:
      #c[i]+=1
  #print('c='+str(c))
  #for i in range(N):
    #b[i]=a[i][c[i]]
  #print('b='+str(b))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()

print('-1')

### FIXED CODE ###

import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
#print(matches)
q = deque(range(n))
#print(q)
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    b = matches[a].pop()
    #print(a, b)
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.append(a)
        if matches[b]:
            q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))
### BUGGY CODE ###

n = int(input())
mlist = []
for i in range(n):
    m = int(input())
    mlist.append(m)
mlist.sort()
plist = [2]
count = 0
j = 2
for i in mlist:
    if (i in plist):
        count += 1  
    else:
        for k in range(j+1, i+1):
            c = 0
            for p in plist:
                if (k % p != 0):
                    c += 1
                else : 
                    break
            if (c == len(plist)):
                plist.append(k)   
                if (k == i):
                    count += 1
    j = i
print(count)  


### FIXED CODE ###

n = int(input())
mlist = []
plist = [2]
for i in range(3,10000):
    count = 0
    for k in plist:
        if (i%k != 0):
            count += 1
        else:
            break
    if (count == len(plist)):
        plist.append(i)
def check(m):
    for p in plist:
        if (m <= p):
            return True
        if m%p == 0:
            return False     ##한번이라도 False가 return되면 False가 되기에 prime인지 아닌지 check가능
    return True

count = 0
for i in range(n):
    m = int(input())
    if check(m):
        count += 1
        
print(count)
### BUGGY CODE ###

S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
s=t.copy()
t[0]=1
jkmap=[]
for j in range(10):
  jkmap.append([])
  for k in range(13):
    jkmap[j].append((10*k+j)%13)
for i in range(n):
  if S[i]=='?':
    tcopy=s.copy()
    for j in range(10):
      for k in range(13):
        tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    t=tcopy.copy()
  else:
    j=int(S[i])
    tcopy=s.copy()
    for k in range(13):
      tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    t=tcopy.copy()
print(t[5])

### FIXED CODE ###

S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
t[0]=1
jkmap=[]
for j in range(10):
  jkmap.append([])
  for k in range(13):
    jkmap[j].append((10*k+j)%13)
for i in range(n):
  if S[i]=='?':
    tcopy=[0]*13
    for j in range(10):
      for k in range(13):
        tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    for j in range(13):
      t[j]=tcopy[j]
  else:
    j=int(S[i])
    tcopy=[0]*13
    for k in range(13):
      tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    for j in range(13):
      t[j]=tcopy[j]
print(t[5])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    print(A[i:].count(i + 1))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A)
for i in range(N): print(c[i + 1])
### BUGGY CODE ###

from itertools import product

N = int(input())
r = range(N)
A = [list(map(int, input().split())) for _ in r]

possible = True
ans = 0
for i,j in product(r, r) :
    if j <= i: continue
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans if possible else -1)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    c = [[0] for i in xrange(m+1)]
    c[0] += [0]*n
    
    for i in xrange(m):
        for j in xrange(n):
            if X[i] == Y[j]:
                c[i+1].append(c[i][j] + 1)
            else:
                if c[i][j+1] >= c[i+1][j]:
                    c[i+1].append(c[i][j+1])
                else:
                    c[i+1].append(c[i+1][j])
    return c[m][n]
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    r1 = [0 for i in xrange(n+1)]
 
    for i in xrange(m):
        r0 = r1[:]
        for j in xrange(n):
            if X[i] == Y[j]:
                r1[j+1] = r0[j] + 1
            elif r0[j+1] < r1[j]:
                r1[j+1] = r1[j]
    return r1[-1]

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

N = int(input())
prize = []
for i in range(N):
    s = str(input())
    if s in prize:
        continue
    else:
        prize.append(s)

print(len(prize))


### FIXED CODE ###

N = int(input())
prize = {}

for i in range(N):
    s = str(input())
    if s in prize:
        continue
    else:
        prize[s] = 1

print(len(prize))
### BUGGY CODE ###

N,W = map(int, input().split())
v_max = 10**5
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,-1,-1):
		if j==0:
			dp[j] = 0
		else:
			a = dp[j]
			b = w + dp[j-v]		
			if v>j:
				dp[j] = a
			else:
				dp[j] = min(a,b)
ans = None
for i in range(v_max,-1,-1):
	z = dp[i]
	if z<=W and z!=inf:
		ans = i
		break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N,W = map(int, input().split())
v_max = (10**3)*N
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,v-1,-1):
		b = w + dp[j-v]		
		if b<dp[j]:
			dp[j] = b

ans = None
for i in range(v_max+1):
	z = dp[i]
	if z<=W:
		ans = i

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

n = int(input())
a = input().split()
j=0
c=0
for i in range(len(a)):
    if(int(a[j])!=j+1):
        del(a[j])
        c+=1
    else:
        j+=1
if(n==c):
    print(-1)
else:
    print(c)

### FIXED CODE ###

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

import sys
input = sys.stdin.readline

n, x, y = [int(x) for x in input().split()]

edge = [[] for _ in range(n)]

for i in range(n - 1):
    edge[i].append([1, i + 1])
    edge[i + 1].append([1, i])

edge[x - 1].append([1, y - 1])
edge[y - 1].append([1, x - 1])

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

d = dijkstra_heap(0)
# print(d)

ans = [0] * (n)
# print(edge)
for i in range(n):
    d = dijkstra_heap(i)
    # print(d)
    for j in d:
        if j != float("inf"):
            ans[j] += 1

for i in range(n):
    ans[i] //= 2

for i in ans[1:]:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, x, y = [int(x) for x in input().split()]

g = [[] for _ in range(n)]

for i in range(n - 1):
    g[i].append(i + 1)
    g[i + 1].append(i)

g[x - 1].append(y - 1)
g[y - 1].append(x - 1)

from collections import deque

def bfs(u):
    d = [-1]*n
    d[u] = 0
    queue = deque([u])
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] < 0:
                d[i] = d[v] + 1
                queue.append(i)
    return d

ans = [0] * n

for i in range(n):
    d = bfs(i)
    for j in d:
        ans[j] += 1

for i in ans[1:]:
    print(i // 2)
### BUGGY CODE ###

N, K =map(int, input().split())
lst=list(map(int, input().split()))
new_lst=[]
mx=0
for i in range(0, N-K+1):
	if mx<sum(lst[i:i+K]):
		mx=sum(lst[i:i+K])

print((mx+K)/2)


### FIXED CODE ###

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

expect=[(dice+1)/2 for dice in p]
#print(expect)
#plus_p=[sum(expect[i:i+K]) for i in range(N-K+1)]

first=sum(expect[0:K])
plus_p=[first]
for i in range(1, N-K+1):
	plus_p.append(plus_p[i-1]-expect[i-1]+expect[i-1+K])
#print(plus_p)
print(max(plus_p))
### BUGGY CODE ###

WIDE = 10**5 + 10

N = int(input())
A = [int(input()) for _ in range(N)]

dp = [[-1] for _ in range(WIDE)]

for i in range(N):
    for j in range(len(dp)):
        if dp[j][-1] < A[i]:
            dp[j].append(A[i])
            break

count = 0
for i in range(WIDE):
    if len(dp[i]) >= 2:
        count += 1
    if len(dp[i]) == 1:
        break       

print(count)

### FIXED CODE ###

import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N
dp[N-1] = A[0]

ans = 0
for i in range(1, N):
    target_index = bisect.bisect_left(dp, A[i])
    dp[target_index-1] = A[i]

print(N - dp.count(-1))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import collections

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
count_rmv = 0
count_int = sorted(collections.Counter(A).values())
num_int_type = len(count_int)

while num_int_type > K:
    count_rmv += count_int[0]
    del count_int[0]
    num_int_type -= 1

print(count_rmv)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import collections

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

count_rmv = 0
count_int = collections.Counter(A).most_common()
num_int_type = len(count_int)

while num_int_type > K:
    num_int_type -= 1
    count_rmv += count_int[num_int_type][1]

print(count_rmv)
### BUGGY CODE ###

import bisect

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

alist = sorted(list(map(int, input().split())))

for _ in range(m):
  b, c = map(int, input().split())
  idx = bisect.bisect_right(alist,c)
  if idx-1 <= b:
    alist = [c for _ in range(idx)] + alist[idx:]
  else:
    new_alist = alist[b:]
    idx2 = bisect.bisect_right(new_alist,c)
    alist = new_alist[:idx2] + [c for _ in range(b)] + new_alist[idx2:]
  
print(sum(alist))

### FIXED CODE ###

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

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num >= N: break
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]) if num != N else ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    a_sum = sum(a)
    if a_sum < sum(b):
        print(-1)
        exit()

    diff = [0] * n
    for i in range(n):
        diff[i] = a[i] - b[i]
    org_diff = diff[:]

    def move(num):
        max_v = max(diff)
        max_i = diff.index(max_v)
        if max_v > num:
            diff[max_i] -= num
        else:
            diff[max_i] = 0
            move(num - max_v)

    for i in range(n):
        if diff[i] >= 0:
            continue
        move(-diff[i])
        diff[i] = 0
    print(sum([1 for i in range(n) if diff[i] != org_diff[i]]))
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    B = map(int, input().split())

    sum = 0
    ans = 0
    rest = []
    for a, b in zip(A, B):
        if b > a:
            sum += b - a
            ans += 1
        else:
            rest.append(a - b)
    rest.sort(reverse=True)

    if sum <= 0:
        print(0)
        exit()

    for r in rest:
        sum -= r
        ans += 1
        if sum <= 0:
            break
    if sum > 0:
        print(-1)
    else:
        print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
ans=0
l=[10**9+1]
import bisect
for i in range(n):
  a=int(input())
  num=bisect.bisect_left(l,a)
  if l[num]==a:
    ans-=1
    del l[num]
  else:
    l.append(a)
    l.sort()
    ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
ans=0
l=[int(input()) for i in range(n)]
from collections import Counter
lst=list(Counter(l).values())
def mod2(n):
  if n%2==1:
    return 1
  else:
    return 0
ans=0
for i in lst:
  ans+=mod2(i)
print(ans)