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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = map(int,input().split())
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

A.sort()
change = sorted(change,key=lambda x:x[1])
change.reverse()

for i in range(M):
    b,c = change[i]
    if A[0] >= c:
        break
    for j in range(b):
        if A[j] < c:
            A[j] = c
        else:
            break
    A.sort()

print(sum(A))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = map(int,input().split())
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

D = []
change = sorted(change,key=lambda x:x[1],reverse=True)
for i in range(M):
    b,c = change[i]
    for j in range(b):
        D += [c]
    if len(D) > N:
        break

A += D
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
max=-2
for i in range(1,n+1):
    if i<b:
        s=math.floor(a*i/b)
    else:
        s=math.floor(a*i/b)-a*math.floor(i/b)
    if s>max:
        max=s
print(int(max))


### FIXED CODE ###

import math
a,b,n=map(int,input().split())
max=-2
if n<b:
    max=math.floor(a*n/b)
else:
    #b<=n
    max=math.floor(a*(b-1)/b)
    

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

import sys
sys.setrecursionlimit(2500)
H, W = map(int, input().split())
S = ['#'*(W+2)]+['#' + input() + '#' for _ in range(H)]+['#'*(W+2)]

ans = [[None] * (W+2) for _ in range(H+2)]
ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (W+2) for _ in range(H+2)]

def process(n, x, y, dx, dy):
  ret = 0
  if S[y][x] == '#':
    ret = n
  else:
    ret = process(n+1, x+dx, y+dy, dx, dy)
  if dx > 0:
    ansX[y][x] = ret
  else:
    ansY[y][x] = ret
  return ret

final = 0
for y in range(1, H+1):
  for x in range(1, W+1):
    if S[y][x] == '#':
      continue
    if ansX[y][x] is None:
      process(0, x, y, 1, 0)
    if ansY[y][x] is None:
      process(0, x, y, 0, 1)
    ans = ansX[y][x] + ansY[y][x] - 1
    final = ans if ans > final else final
print(final)

### FIXED CODE ###

H, W = map(int, input().split())
S = ['#'*(W+2)]+[
  '#' + input() + '#' for _ in range(H)
]+['#'*(W+2)]

ST = list(map(''.join, zip(*S)))

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (H+2) for _ in range(W+2)]

final = 0
for y in range(1, H+1):
  Sy = S[y]
  ansXy = ansX[y]
  #ansYy = ansY[y]
  for x in range(1, W+1):
    if Sy[x] == '#':
      continue
    if ansX[y][x] is None:
      t = Sy.find('#', x)
      ansXy[x:t] = [t-x] * (t-x)
    if ansY[x][y] is None:
      t = ST[x].find('#', y)
      ansY[x][y:t] = [t-y] * (t-y)
    a = ansXy[x] + ansY[x][y] - 1
    final = a if a > final else final
print(final)
### BUGGY CODE ###

from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = A
    num_cards = len(cards)
    for s in S:
        b = s[0]
        c = s[1]
        for _ in range(b):
            min_card_num = min(cards)
            if c > min_card_num:
                for i in range(num_cards):
                    if cards[i] == min_card_num:
                        cards[i] = c
                        break
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

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

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    c = input()
    ans = INF
    for i in range(n+1):
        w = c[:i].count("W")
        r = c[i:].count("R")
        ans = min(ans, max(w,r))
    print(ans)

if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    c = input()
    r = c.count("R")
    ans = 0
    for i in range(r, n):
        if c[i] == "R":
            ans += 1
    print(ans)

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

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

n = int(input())
xy = [[[] for _ in range(10**5+1)] for __ in range(2)]

for _ in range(n):
    x,y = map(int,input().split())
    xy[0][x].append(y)
    xy[1][y].append(x)

ans = 0
used = [[False for _ in range(10**5+1)] for __ in range(2)]

def dfs(i,flag):
    for v in xy[flag][i]:
        if not used[1-flag][v]:
            used[1-flag][v] = True
            dfs(v,1-flag)
            count[1-flag] += 1

for i in range(10**5+1):
    if xy[0][i] and not used[0][i]:
        used[0][i] = True
        count = [1,0]
        dfs(i,0)
        ans += count[0]*count[1]

ans -= n
print(ans)

### FIXED CODE ###

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

n = int(input())
xy = [[[] for _ in range(10**5+1)] for __ in range(2)]

for _ in range(n):
    x,y = map(int,input().split())
    xy[0][x].append(y)
    xy[1][y].append(x)

ans = 0
used = [[False for _ in range(10**5+1)] for __ in range(2)]

def dfs(i,flag):
    for v in xy[flag][i]:
        if not used[1-flag][v]:
            used[1-flag][v] = True
            dfs(v,1-flag)
            count[1-flag] += 1

for i in range(10**5+1):
    if xy[0][i] and not used[0][i]:
        used[0][i] = True
        count = [1,0]
        dfs(i,0)
        ans += count[0]*count[1]

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

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,K = list(map(int, input().split()))
# h = list(map(int, input().split()))

# (N,K), h = map(int, input().split()), list(map(int, input().split()))
N,K,*h = map(int, "\n".join([input(), input()]).split())

# suml = [1e9 for i in range(N)]
# suml[0] = 0


suml = [0]*N

for i in range(1,N):

    start = max(0, i-K)
    cost  = min(cst + abs( h[i] - hgh ) for cst, hgh in 
                  zip(suml[start:i], h[start:i]))
    suml[i] = cost

print(suml[-1])
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,K = list(map(int, input().split()))
# h = list(map(int, input().split()))

# (N,K), h = map(int, input().split()), list(map(int, input().split()))
N,K,*h = map(int, "\n".join([input(), input()]).split())

# suml = [1e9 for i in range(N)]
# suml[0] = 0


suml = [0]*N

# for i in range(1,N):
for i,e_h in enumerate(h):
    if i == 0:
        continue

    start = max(0, i-K)
    cost  = min(cst + abs( e_h - hgh) for cst, hgh in 
                   zip(suml[start:i], h[start:i]))
    # cost  = min(cst + abs( h[i] - hgh ) for cst, hgh in 
    #               zip(suml[start:i], h[start:i]))
    suml[i] = cost

print(suml[-1])
### BUGGY CODE ###

n = int(input())
strings = []
nums = []
for i in range(n):
    string = input()
    if string not in strings:
        strings.append(string)
        nums.append(1)
    else:
        nums[strings.index(string)] += 1

l = []
Mx = max(nums)
for i in range(len(strings)):
    if nums[i] == Mx:
        l.append(strings[i])
l.sort()

for i in l:
    print(i)

### FIXED CODE ###

n = int(input())
dic = {}
for i in range(n):
    string = input()
    if string not in dic:
        dic[string] = 1
    else:
        dic[string] += 1

Mx = max(dic.values())
ans = []
for key in dic.keys():    
    if dic[key] == Mx:
        ans.append(key)
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

S=list(input())
N=len(S)
dp=[[0]*13 for i in range(N+1)]
dp[0][0]=1
mod=10**9+7
for i in range(1,N+1):
  for j in range(13):
    if dp[i-1][j]>0:
      if S[i-1]=="?":
        for k in range(10):
          dp[i][(j*10+k)%13]+=dp[i-1][j]
          dp[i][(j*10+k)%13]%=mod
      else:
        dp[i][(j*10+int(S[i-1]))%13]+=dp[i-1][j]
        dp[i][(j*10+int(S[i-1]))%13]%=mod
print(dp[N][5])


         
        
      
    


### FIXED CODE ###

S=list(input())
N=len(S)
dp=[[0]*13 for i in range(N+1)]
dp[0][0]=1
mod=10**9+7
for i in range(1,N+1):
  for j in range(13):
    if dp[i-1][j]>0:
      if S[i-1]=="?":
        for k in range(10):
          dp[i][(j*10+k)%13]+=dp[i-1][j]
          dp[i][(j*10+k)%13]%=mod
      else:
        dp[i][(j*10+int(S[i-1]))%13]+=dp[i-1][j]
        dp[i][(j*10+int(S[i-1]))%13]%=mod
print(dp[N][5])
### BUGGY CODE ###

n, m = map(int, input().split())
 
a_list = []
b_list = []
for i in range(n):
    a,b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
 
ans = 0
for i in range(m):
    i = i+1
    if min(a_list) <= i:
        # ind = a_list.index(max(b_list[list(map(lambda x : x < i+1,b_list))]))
        max_num = max( map(lambda y: y[0] * (y[1] <=i) ,zip(b_list,a_list)))
        # ind = a_list.index(max(b_list * list(map(lambda x : x <= i,a_list))))
        ind = b_list.index(max_num)
        ans = ans + b_list[ind]
        a_list[ind] = m + 1
 
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
db = []

for i in range(n):
    a,b = map(int,input().split())
    if(a<=m):
        db.append([m-a,-1*b])

db.sort(reverse=True)

# ヒープキュー（最小値・最大値の取得）
import heapq
a=[]
heapq.heapify(a)

ans = 0
pnt = 0
day = m-1
while(day>=0):
    if(pnt < len(db)):
        while(db[pnt][0] == day):
            heapq.heappush(a,db[pnt][1])
            pnt += 1
            if(pnt == len(db)):
                break
    day -= 1

    if(len(a) > 0):
        ans -= heapq.heappop(a)

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from heapq import heappop as hpp, heappush as hp
q = []
hp(q, (0,x1,y1,(0,0),0))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[None]*w for _ in range(h)]
dist[x1][y1] = 0
done = [[0]*w for _ in range(h)]
done[x1][y1] = 15

while q:
    d, x, y, t, td = hpp(q)
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if dist[nx][ny] is None or nd<dist[nx][ny]:
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            dist[nx][ny] = nd
            done[nx][ny] = 1<<(i)
        elif nd==dist[nx][ny]and ((done[nx][ny]&1<<(i))==0):
            hp(q, (nd,nx,ny,(xx,yy),ntd))
            done[nx][ny] |= 1<<(i)
            
if dist[x2][y2] is None:
    print(-1)
else:
    print(dist[x2][y2])

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q0 = deque([(0,x1,y1,(0,0),0)])
q1 = deque()

dx = [0,1,0,-1]
dy = [1,0,-1,0]
# dist = [[None]*w for _ in range(h)]
dist = [None]*(w*h)
dist[x1*w+y1] = 0
# done = [[0]*w for _ in range(h)]
done = [0]*(w*h)
done[x1*w+y1] = 15

while q0 or q1:
    if not q0:
        q0 = q1
        q1 = deque()
    d, x, y, t, td = q0.popleft()
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w or s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
            q = q0
        else:
            nd = d+1
            ntd = 1
            q = q1
        if dist[nx*w+ny] is None or nd<dist[nx*w+ny]:
            q.append((nd,nx,ny,(xx,yy),ntd))
            dist[nx*w+ny] = nd
            done[nx*w+ny] = 1<<(i)
        elif nd==dist[nx*w+ny]and ((done[nx*w+ny]&1<<(i))==0):
            q.append((nd,nx,ny,(xx,yy),ntd))
            done[nx*w+ny] |= 1<<(i)
            
if dist[x2*w+y2] is None:
    print(-1)
else:
    print(dist[x2*w+y2])
### BUGGY CODE ###

import math
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
for i in range(m):
    a[a.index(max(a))] = int((max(a) / 2) // 1)
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    k = heapq.heappop(a)
    heapq.heappush(a, -int(-(k / 2) // 1))
print(-sum(a))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

for i in range(n):
	if a.count(a[i]) > 1:
		print("NO")
		exit()

print("YES")

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

if len(a) == len(set(a)):
	print("YES")
else:
	print("NO")
### BUGGY CODE ###

from bisect import bisect_left, bisect_right


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
                
    return divisors

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    B = set(A)
    for a in B:
        flag = False
        left = bisect_left(A, a)
        right = bisect_right(A, a)

        if right-left > 1:
            continue

        divs = make_divisors(a)
        for d in divs:
            if d in B and d != a:
                flag = True
                break

        if flag == False:
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def solve(A):
    n = A[-1]
    is_nodiv = [True for _ in range(n+1)]

    pre = 0
    for a in A:
        if pre == a or not is_nodiv[a]:
            is_nodiv[a] = False
            continue

        for j in range(2*a, n+1, a):
            is_nodiv[j] = False
        
        pre = a
        
    return sum([is_nodiv[a] for a in A])



def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = solve(A)
    print(ans)

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

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

a_i = [0] * n

day = 0
while True:
    matches = []
    has_match = False
    for i in range(n):
        if a_i[i] == n - 1:
            continue
        match = {i+1, a[i][a_i[i]]}
        if match in matches:
            lst = list(match)
            a_i[lst[0] - 1] += 1
            a_i[lst[1] - 1] += 1
            has_match = True
        else:
            matches.append(match)
    if has_match:
        day += 1
        if all([a_i[i] == n - 1 for i in range(n)]):
            break
    else:
        day = -1
        break

print(day)


### FIXED CODE ###

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


match_sm = n * (n - 1) // 2

adj = [[] for _ in range(match_sm)]
in_deg = [0] * match_sm
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [i for i, e in enumerate(in_deg) if e == 0]
day = 0
while cnd:
    nxt_cnd = []
    for u in cnd:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt_cnd.append(v)

    cnd = nxt_cnd
    day += 1

if in_deg.count(0) != match_sm:
    day = -1

print(day)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [None]*n
for i in range(n):
    a[i] = int(input())
ans = a[0]-1
prev = 1
for i,num in enumerate(a[1:]):
    if prev+1<num:
        while num-(prev+1)>0:
            num -= (prev+1)
            ans += 1
            if num==prev+1:
                num = prev
                break
    prev = max(prev, num)
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [None]*n
for i in range(n):
    a[i] = int(input())
ans = a[0]-1
prev = 1
for i,num in enumerate(a[1:]):
    if prev+1<num:
        while num-(prev+1)>0:
            v = (num-1)//(prev+1)
            num -= v*(prev+1)
            ans += v
            if num==prev+1:
                num = prev
                break
    prev = max(prev, num)
print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

def denpan(oya,ko):
    for i in range(len(ne[ko])):
        if ne[ko][i]!=oya:
            cnt[ne[ko][i]]+=cnt[ko]
            denpan(ko,ne[ko][i])

ne=[[] for i in range(n+1)]
for i in range(n-1):
    ne[ab[i][0]].append(ab[i][1])
    ne[ab[i][1]].append(ab[i][0])
# print(ne)
cnt=[0]*(n+1)
for i in range(q):
    cnt[px[i][0]]+=px[i][1]
# print(cnt)
denpan(1,1)
for i in range(1,n+1):
    print(cnt[i])

### FIXED CODE ###

import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

# def denpan(oya,ko):
#     for i in range(len(ne[ko])):
#         if ne[ko][i]!=oya:
#             cnt[ne[ko][i]]+=cnt[ko]
#             denpan(ko,ne[ko][i])

ne=[[] for i in range(n+1)]
for i in range(n-1):
    ne[ab[i][0]].append(ab[i][1])
    ne[ab[i][1]].append(ab[i][0])
# print(ne)
cnt=[0]*(n+1)
for i in range(q):
    cnt[px[i][0]]+=px[i][1]
par=[-1]*(n+1)
stack=deque([1])
while(stack):
    v=stack.pop()
    for i in range(len(ne[v])):
        if ne[v][i]!=par[v]:
            cnt[ne[v][i]]+=cnt[v]
            par[ne[v][i]]=v
            stack.append(ne[v][i])
cnt.remove(0)
print(' '.join(map(str,cnt)))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
n=int(input())
v=[int(x) for x in input().split()]
if len(set(v))==1:
    print(n//2)
    import sys
    sys.exit()
from collections import Counter
v1=[]
v2=[]
for i in range(n):
    if i%2==0:
        v1.append(v[i])
    else:
        v2.append(v[i])
v1=Counter(v1)
v2=Counter(v2)
ans=10**10
# print(v1,v2)
for i1 in v1.most_common():
    for i2 in v2.most_common():
        # print(n-i1[1]-i2[1],i1,i2)
        ans=min(n-i1[1]-i2[1],ans)
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
n=int(input())
v=[int(x) for x in input().split()]
if len(set(v))==1:
    print(n//2)
    import sys
    sys.exit()
from collections import Counter
v1=[]
v2=[]
for i in range(n):
    if i%2==0:
        v1.append(v[i])
    else:
        v2.append(v[i])
v1=Counter(v1)
v2=Counter(v2)
ans=10**10
# print(v1,v2)
for i1 in v1.most_common(min(len(v1),10)):
    for i2 in v2.most_common(min(len(v1),10)):
        # print(n-i1[1]-i2[1],i1,i2)
        if i1==i2:
            continue
        ans=min(n-i1[1]-i2[1],ans)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

dp = [-1]*(N+1)
dp[0] = 1
ans = 0

for i in range(1, N+1):
    if i in a:
        dp[i] = 0
        if dp[i-1] == 0:
            ans = 0
            break
    else:
        if i > 1:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = dp[i-1]

else:
    ans = dp[-1] % 1000000007

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

dp = [-1]*(N+1)
for i in a:
    dp[i] = 0

dp[0] = 1
mod = 1000000007

for i in range(1, N+1):
    if dp[i] == 0:
        continue
    else:
        if i > 1:
            dp[i] = (dp[i-1] + dp[i-2]) % mod
        else:
            dp[i] = dp[i-1] % mod

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

import math

K = int(input())+1
ans = 0
for i in range(1,K):
    for j in range(1,K):
        for k in range(1,K):
            ans += math.gcd(math.gcd(i, j),k)
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input()) + 1
ans = 0
for i in range(1,k):
  for j in range(1,k):
    for l in range(1,k):
      ans += gcd(gcd(i, j),l)
print(ans)
### BUGGY CODE ###

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

for i in range(N):
    print(emp.count(i+1))


### FIXED CODE ###

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

X,Y,Z,K=map(int,input().split())
if X>Y and X>Z:
  X,Z=Z,X
  A,C=C,A
elif Y>X and Y>Z:
  Y,Z=Z,Y
  B,C=C,Y
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
k=min(K,X*Y)
AB=sorted([a+b for a in A for b in B],reverse=True)[:k]
ABC=sorted([ab+c for ab in AB for c in C],reverse=True)[:K]
for x in ABC:
  print(x)

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
B=sorted(list(map(int,input().split())),reverse=True)
C=sorted(list(map(int,input().split())),reverse=True)
ans=[]
for i in range(X):
  if i+1>K:
    break
  for j in range(Y):
    if (i+1)*(j+1)>K:
      break
    for k in range(Z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      ans.append(A[i]+B[j]+C[k])
ans=sorted(ans,reverse=True)
for a in ans[:K]:
  print(a)
### BUGGY CODE ###

N = int(input())
numbers = [int(input()) for i in range(N)]

def check_max_num(i,numbers):
    max_num = 0
    for j in range(len(numbers)):
        if j != i:
            if numbers[j] > max_num:
                max_num = numbers[j]
    return max_num

for i in range(len(numbers)):
    print(check_max_num(i,numbers))

### FIXED CODE ###

N = int(input())
numbers = [int(input()) for i in range(N)]

# 最大値を取得
max_num = max(numbers)

# 最大値を同じ値がいくつ在るかを確認
max_nums = numbers.count(max_num)

if max_nums >= 2:
    for i in range(len(numbers)):
        print(max_num)
else :
    max_index = numbers.index(max(numbers))
    for i in range(len(numbers)):
        if i == max_index:
            second_max = sorted(numbers)[-2]
            print(second_max)
        else :
            print(max_num)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
x=[i for i in a if a.count(i)%2!=0]
print(len(x))

### FIXED CODE ###

import numpy
n=int(input())
a=[int(input()) for _ in range(n)]
b=set()
for i in range(n):
    if a[i] in b:
      b.remove(a[i])
    else:
      b.add(a[i])
print(len(b))