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

import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())

        blacks = []
        field = defaultdict(lambda: '#')
        for h in range(H):
            for w, c in enumerate(input().rstrip()):
                field[self.key((h + 1, w + 1))] = c
                if c == '#':
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        while blacks:
            next_blacks = []
            for b_h, b_w in blacks:
                for m_h, m_w in moving_range:
                    target = (b_h + m_h, b_w + m_w)
                    if field[self.key(target)] == '.':
                        field[self.key(target)] = '#'
                        next_blacks.append(target)
            if len(next_blacks) > 0:
                ans += 1
            blacks = next_blacks

        print(ans)

    def key(self, pos):
        return str(pos[0]) + '-' + str(pos[1])


# Run main
if __name__ == '__main__':
    AtCoder().main()

### FIXED CODE ###

import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        A = [list(input().rstrip()) for _ in range(H)]

        blacks = []
        for h in range(H):
            for w in range(W):
                if A[h][w] == '#':
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        while blacks:
            next_blacks = []
            for b_h, b_w in blacks:
                for m_h, m_w in moving_range:
                    h, w = b_h + m_h, b_w + m_w
                    if not (0 < h <= H and 0 < w <= W):
                        continue
                    if A[h-1][w-1] == '.':
                        A[h-1][w-1] = '#'
                        next_blacks.append((h, w))
            if len(next_blacks) > 0:
                ans += 1
            blacks = next_blacks

        print(ans)


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


def main():
    N = int(input())
    S = input()

    for i in range(N // 2, max(N // 2 - 100, 0), -1):
        for j in range(N - i + 1):
            if S.find(S[j: i + j], i + j) > 0:
                print(i)
                exit()

    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        check = set()
        for i in range(N - x + 1):
            check.add(S[i: i + x])
            if S[i + x: i + 2 * x] in check:
                ok = x
                break
        else:
            ng = x

    print(ok)


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

def main():
    X, Y, A, B, C = tuple(map(int, input().split()))
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    R = list(map(int, input().split()))

    P = sorted(P, reverse=True)
    Q = sorted(Q, reverse=True)
    R = sorted(R, reverse=True)

    x = P[:X]
    y = Q[:Y]

    for r_i in R:
        if r_i < min(x[-1], y[-1]):
            break
        else:
            if x[-1] < y[-1]:
                x[-1] = r_i
                x = sorted(x, reverse=True)
            else:
                y[-1] = r_i
                y = sorted(y, reverse=True)

    print(sum(x) + sum(y))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X, Y, A, B, C = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    Q = tuple(map(int, input().split()))
    R = tuple(map(int, input().split()))

    P = sorted(P, reverse=True)
    Q = sorted(Q, reverse=True)
    R = sorted(R, reverse=True)

    x = P[:X]
    y = Q[:Y]

    saikyo = sorted(x + y + R, reverse=True)
    print(sum(saikyo[:(X + Y)]))


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

import math

def F(A,B):
    if A > B:
        return len(str(A))
    else:
        return len(str(B))
            

N = int(input())
min = F(1,N)
rt = int(math.sqrt(N))
for i in range(rt,N+1):
    if N % i != 0:
        continue
    f = F(i,int(N/i))
    if f < min:
        min = f
        break
print(min)

### FIXED CODE ###

import math

def F(A,B):
    if A > B:
        return len(str(A))
    else:
        return len(str(B))
            

N = int(input())
min = F(1,N)
rt = int(math.sqrt(N))
for i in range(2,rt+1):
    if N % i != 0:
        continue
    f = F(i,int(N/i))
    if f < min:
        min = f
print(min)
### BUGGY CODE ###

import array
n,t = map(int,input().split())
a = list(map(int,input().split()))
a = array.array("i",a)
ans = []
flag = max(a)
flag_2 = a.index(flag)
for i in range(n):
  if i <= flag_2:
    ans.append(flag-a[i])
  else:
    flag = max(a[i:n])
    flag_2 = a.index(flag)
    ans.append(flag-a[i])
print(ans.count(max(ans)))

### FIXED CODE ###

n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = float("inf")
for i in range(n):
    flag = min(flag,a[i])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))
### BUGGY CODE ###

import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    s = input()
    q = int(input())
    ans = deque()
    swap = False
    for i in range(len(s)):
        ans.append(s[i])

    for i in range(q):
        #print(ans, swap)
        inp = input()
        if len(inp) == 1:
            hoge = int(inp)
            if swap:
                swap = False
            else:
                swap = True
        else:
            # print(tuple(inp))
            fi, ci = tuple(inp)[2], tuple(inp)[4]
                       
            if int(fi) == 1:
                if not swap:
                    ans.appendleft(ci)
                else:
                    ans.append(ci)
            if int(fi) == 2:
                if not swap:
                    ans.append(ci)
                else:
                    ans.appendleft(ci)
    s_ans = str()
    ans = list(ans)
    if swap:
        for i in range(len(ans)-1,-1, -1):
            s_ans = s_ans +  ans[i]
    else:
        for i in range(len(ans)):
            s_ans = s_ans + ans[i]
    
    print(s_ans)
                
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    s = input()
    q = int(input())
    ans = deque()
    swap = False
    for i in range(len(s)):
        ans.append(s[i])

    for i in range(q):
        #print(ans, swap)
        inp = input()
        if len(inp) == 1:
            hoge = int(inp)
            if swap:
                swap = False
            else:
                swap = True
        else:
            # print(tuple(inp))
            fi, ci = tuple(inp)[2], tuple(inp)[4]
                       
            if int(fi) == 1:
                if not swap:
                    ans.appendleft(ci)
                else:
                    ans.append(ci)
            if int(fi) == 2:
                if not swap:
                    ans.append(ci)
                else:
                    ans.appendleft(ci)
    s_ans = str()
    ans = list(ans)
    if swap:
        for i in range(len(ans)-1,-1, -1):
            s_ans += ans[i]
    else:
        for i in range(len(ans)):
            s_ans += ans[i]
    
    print(s_ans)
                
    return

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

X,Y,Z,K=map(int,input().split())
Ax=sorted(list(map(int,input().split())), reverse=True)
By=sorted(list(map(int,input().split())), reverse=True)
Cz=sorted(list(map(int,input().split())), reverse=True)

a=b=c=0
s = [(a,b,c)]
t = set()
for k in range(K):
    best_value = 0
    best_tuple = None
    for x,y,z in s:
        if (x,y,z) not in t:
            m = Ax[x]+By[y]+Cz[z]
            if m > best_value:
                best_value = m
                best_tuple = (x,y,z)
    print(best_value)

    t.add(best_tuple)
    s.remove(best_tuple)
    x,y,z=best_tuple
    if x < X-1:
        s.append((x+1,y,z))
    if y < Y-1:
        s.append((x,y+1,z))
    if z < Z-1:
        s.append((x,y,z+1))


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
Ax=sorted(list(map(int,input().split())), reverse=True)
By=sorted(list(map(int,input().split())), reverse=True)
Cz=sorted(list(map(int,input().split())), reverse=True)

a=b=c=0
s = set([(a,b,c)])
t = set()
for k in range(K):
    best_value = 0
    best_tuple = None
    for x,y,z in s:
        if (x,y,z) not in t:
            m = Ax[x]+By[y]+Cz[z]
            if m > best_value:
                best_value = m
                best_tuple = (x,y,z)
    print(best_value)

    t.add(best_tuple)
    s.remove(best_tuple)
    x,y,z=best_tuple
    if x < X-1:
        if (x+1,y,z) not in s:
            s.add((x+1,y,z))
    if y < Y-1:
        if (x,y+1,z) not in s:
            s.add((x,y+1,z))
    if z < Z-1:
        if (x,y,z+1) not in s:
            s.add((x,y,z+1))
### BUGGY CODE ###

import sys
from  heapq import heappush, heappop, heapify

N=int(input())

par=[ i for i in range(N) ]

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

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y



X=[]
Y=[]
for i in range(N):
	x,y=map(int, sys.stdin.readline().split()) 
	X.append( (x,i) )
	Y.append( (y,i) )

X.sort(key=lambda x: x[0])
Y.sort(key=lambda x: x[0])

hq=[]

prev_x=None
prev_i=None
for x,i in X:
	if prev_x is not None:	
		heappush( hq, ( x-prev_x, i, prev_i) )
	prev_x=x
	prev_i=i

prev_x=None
prev_i=None
for x,i in Y:
	if prev_x is not None:	
		heappush( hq, ( x-prev_x, i, prev_i) )
	prev_x=x
	prev_i=i


ans=0
while hq:
	d,a,b=heappop(hq)
	if not same(a,b):
		ans+=d
		unite(a,b)
		
print (ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
import sys
sys.setrecursionlimit(10**6)
N = input()
a = []
for i in range(N):
	x,y=map(int,raw_input().split())
	a.append((i,x,y))

#a => point,x,y
a1=sorted(a, key=lambda x: x[1])
a2=sorted(a, key=lambda x: x[2])


#Union Find
#初めは各頂点が根
par=[ i for i in range(N) ]
#木の根を求める
def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		#経路圧縮
		par[x]=r
		return r
#xとyが同じ集合に属するか
def same(x,y):
	return root(x)==root(y)

#xとyが同じ根に所属していた場合、連結
def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	else:
		par[x]=y


b=[]
for i in range(N-1):
	# len_x,x,y
	heapq.heappush( b, ( abs(a1[i+1][1]-a1[i][1]),a1[i][0],a1[i+1][0],  ))

for i in range(N-1):
	# len_y,x,y
	heapq.heappush( b, ( abs(a2[i+1][2]-a2[i][2]),a2[i][0],a2[i+1][0],  ))

#print "# b"
#print b


ans=0
cnt=0
for i in range(len(b)):
	if cnt==N-1:
		break
	val=heapq.heappop(b)
	#２点が同じ根でない場合は、木を結合する
	if not same(val[1],val[2]):
		unite(val[1],val[2])
		ans+=val[0]
		cnt+=1

print ans
### BUGGY CODE ###

INF = 10 ** 5
N, Ma, Mb = map(int,input().split())
dp = [[[INF for i in range(10 * N + 1)] for j in range(10 * N + 1)] for k in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    a, b, c = map(int,input().split())
    for j in range(10 * N + 1):
        for k in range(10 * N + 1):
            dp[i+1][j][k] = min(dp[i][j][k], dp[i+1][j][k])
            if j + a <= 10 * N and k + b <= 10 * N:
                dp[i+1][j+a][k+b] = min(dp[i][j][k] + c, dp[i+1][j+a][k+b])

ans = INF
i = 1
while Ma * i <= 10 * N and Mb * i <= 10 * N:
    ans = min(ans, dp[N][Ma*i][Mb*i])
    i += 1

if ans == INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

INF = 10 ** 5
N, Ma, Mb = map(int,input().split())
dp = [[[INF for i in range(10 * N + 1)] for j in range(10 * N + 1)] for k in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    a, b, c = map(int,input().split())
    for j in range(10 * N + 1):
        for k in range(10 * N + 1):
            dp[i+1][j][k] = min(dp[i][j][k], dp[i+1][j][k])
            if j + a <= 10 * N and k + b <= 10 * N:
                dp[i+1][j+a][k+b] = min(dp[i][j][k] + c, dp[i+1][j+a][k+b])

ans = INF
i = 1
while Ma * i <= 10 * N and Mb * i <= 10 * N:
    ans = min(ans, dp[N][Ma*i][Mb*i])
    i += 1

if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

S=input()
N=len(S)
childs=[1]*N
result=[0]*N

for i in range(N):
  if S[i]=="R": # その子がRにいる場合。右に探しに行く
    #次に出会うLを探す
    j = i
    count = 0 # 何歩歩いたか
    for j in range(j+1,N): # 右に探す旅
      count = count + 1
      if S[j] == "L":#Lにぶつかった
        #そのときの歩数が偶数なら、j番目に落ち着く
        if count%2 == 0:
          result[j] = result[j] + 1
        #そのときの歩数が奇数ならj-1番目に落ち着く
        else:
          result[j-1] = result[j-1] + 1
        break # 右に探す旅を終える
  else: # その子がLにいる場合。左に探しに行く
    j = i #添え字をjに代入
    count = 0 #何歩歩いたか
    for j in range(j-1,-1,-1):
      count = count + 1
      if S[j] == "R": # Rにぶつかった
        # そのときの歩数が偶数なら、j番目に落ち着く
        if count%2 == 0:
          result[j] = result[j] + 1
        # そのときの歩数が奇数ならj+1番目に落ち着く
        else:
          result[j+1] = result[j+1] + 1
        break # 左に探す旅を終える


result_str = [str(n) for n in result]
print(" ".join(result_str))


### FIXED CODE ###

s=input()
ans=[0]*len(s)
import itertools
i=0
for key,g in itertools.groupby(s):
  num=len(list(g))
  if key=="R":
    i+=num
    ans[i-1]+=(num//2+(num%2>0))
    ans[i]+=num//2
  elif key=="L":
    ans[i-1]+=num//2
    ans[i]+=(num//2+(num%2>0))
    i+=num
  if i>=len(ans):
    break
print(*ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    Query.append([c,b])
Query.sort(reverse=True)
for i in range(m):
    b,c = Query[i][1],Query[i][0]
    if A[0] >= c:
        break
    else:
        #A.sort()
        index = bisect.bisect_left(A,c)
        if b <= index:
            #for i in range(b):
            #    A[i] = c
            A = A[b:index] + [c for i in range(b)] + A[index:]
        else:
            #for i in range(index):
            #    A[i] = c
            A = [ c for i in range(index)] + A[index:]
    #print(A)
print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    #print("----")
    cnt = 0
    Flag = True
    while Flag:
        #print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))
### BUGGY CODE ###

import sys
count = int(sys.stdin.readline())
zenbu = []

for x in range(count):
    keihin = sys.stdin.readline()

    if not keihin in zenbu:
        zenbu.append(keihin)
print(len(zenbu))


### FIXED CODE ###

count = int(input())
zenbu = set()
 
for x in range(count):
    keihin = input()
    zenbu.add(keihin)
print(len(zenbu))
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(0,n):
    if p[i]==min(p[:i+1]):
        ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
m = 200001
for i in p:
    if i<m:
        ans+=1
        m=i
print(ans)
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        waru = 4 * h * n - N * n - N * h
        if waru != 0:
            w = (N * h * n) / waru
            if w > 0 and int(w) / w == 1:
                print("{} {} {}".format(h, n, int(w)))
                exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        waru = 4 * h * n - N * n - N * h
        if waru != 0:
            w = (N * h * n) / waru
            if w > 0 and int(w) / w == 1:
                print("{} {} {}".format(h, n, int(w)))
                exit()
### BUGGY CODE ###

num=int(input().rstrip())
m=input().rstrip().split()
main=[]
for i in m:
    main.append(int(i))
sample=sorted(main,reverse=True)
new=[]
plusold=0
result=0
for i in range(num):
    if len(new)==0:
        new.append(sample[i])
    elif len(new)<=2:
        new.append(sample[i])
        result+=sample[i-1]
    else:
        plus=new[len(new)-1]
        point=len(new)
        for j in range(len(new)-1):
            if plus<new[j] and plus<new[j+1]:
                plus=min([new[j],new[j+1]])
                point=j+1
                if plus==plusold:
                    break
        result+=plus
        plusold=plus
        if point==len(new):
            new.append(sample[i])
        else:
            new.insert(point,sample[i])
print(result)


### FIXED CODE ###

num=int(input().rstrip())
m=input().rstrip().split()
main=[]
for i in m:
    main.append(int(i))
sample=sorted(main,reverse=True)
result=0
for i in range(2,num+1):
    if i%2==0:
        y=i/2-1
        result+=sample[int(y)]
    else:
        y=(i+1)/2-1
        result+=sample[int(y)]
print(result)
### BUGGY CODE ###

n = int(input())

a_i_list = []

push_i = 1
GOAL_i = 2

is_loop = False
pushed_i_list = []

push_counter = 0

for i in range(n):
  a_i_list.append(int(input()))


while (True):
  push_counter += 1

  pushed_i_list.append(push_i)

  push_i = a_i_list[push_i-1]

  if push_i in pushed_i_list:
    push_counter = -1
    break
  
  if push_i == GOAL_i:
    break


print(push_counter)

### FIXED CODE ###

n = int(input())

a_i_list = []

push_i = 1
GOAL_i = 2

is_loop = False
pushed_i_list = []

push_counter = 0

for i in range(n):
  a_i_list.append(int(input()))

while (True):
  push_counter += 1

  # pushed_i_list.append(push_i)
  current_index = push_i - 1
  push_i = a_i_list[push_i - 1]
  
  # 一度使用したボタンは数値を0にする
  a_i_list[current_index] = 0

  if a_i_list[push_i - 1] == 0:
    push_counter = -1
    break
  
  if push_i == GOAL_i:
    break


print(push_counter)
### BUGGY CODE ###

def main():
    
    n,k=map(int,input().split())
    h=list(map(int,input().split()))

    dp=[9999999999]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])

    for i in range(2,n):
        for j in range(1,k+1):
            if i-j>=0:
                dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
            else:
                break

    print(dp[n-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
 
    # dp=[9999999999]*n
    # dp[0]=0
    # dp[1]=abs(h[1]-h[0])
 
    # for i in range(2,n):
    #     for j in range(1,k+1):
    #         if i-j>=0:
    #             dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
    #         else:
    #             break
 
    # print(dp[n-1])
 
 
    #part2
 
    dp=[9999999999]*n
    dp[0]=0
 
    for i in range(n):
        for j in range(1,k+1):
            if i+j<n:
                dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
            else:
                break
 
    print(dp[n-1])
 
 
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def is_ok(arg):
    if l[arg] < tmp_sum:
        return True
    return False

def meguru_binary_search(ng, ok):
    while abs(ng - ok) > 1:
        mid = (ng + ok) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

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

l.sort()
l += [1001001001]

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        tmp_sum = l[i] + l[j]
        c = meguru_binary_search(n, j)
        ans += c-j

print(ans)


### FIXED CODE ###

from bisect import bisect_left

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

l.sort()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        tmp = bisect_left(l, l[i]+l[j]) - 1
        ans += tmp - j

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

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

for k in range(N):
  A0=A[0]
  A.remove(A0)

  print(max(A))
  A.append(A0)

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=sorted(A)
A0=B[N-1]
A1=B[N-2]
for i in range(N):
  if A[i]!=A0:
    print(A0)
  else:
    print(A1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    MOD = 998244353

    dp = [0] * (s + 1)
    dp[0] = 1

    for i in a:
        p = [0] * (s + 1)
        dp, p = p, dp
        for j in range(s + 1):
            dp[j] += (p[j] * 2) % MOD
            dp[j] %= MOD
            if j + i <= s:
                dp[j + i] += p[j]
                dp[j + i] %= MOD

    print(dp[s])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    A = [int(i) for i in input().split()]

    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for a in A:
        p = (dp * 2) % MOD
        p %= MOD
        p[a:] += dp[:-a]
        dp = p % MOD

    print(dp[s])


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

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))
B=set(A)
# print(A)
# print(B)

ct=0
for i in B:
  if A.count(i)%2==1:
    ct+=1
print(ct)

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))
A.sort()
# print(A)

# 想定解で解くしかない
res=0
i=0
while i<N:
  c=A[i]
  f=0
  while i<N and A[i]==c:
    f+=1
    i+=1
  res+=f%2
print(res)
### BUGGY CODE ###

MOD = 998244353

n = int(input())
distances = list(map(lambda x: int(x), input().split()))

# 最初が0であることを確認
canSolve = True
ans = 1

if distances[0] != 0:
    canSolve = False
    ans = 0

dist_list = {}
if canSolve:
    for i in distances:
        if i in dist_list.keys():
            dist_list[i] += 1
        else:
            dist_list[i] = 1
            
            
    keys = list(dist_list.keys())
    keys.sort()
    keys.reverse()
    bigger = None
    smaller = None
    for v in keys:
        if bigger is None:
            bigger = dist_list[v]
            continue
        elif smaller is None:
            smaller = dist_list[v]
        else:
            bigger = smaller
            smaller = dist_list[v]
        
        ans *= (smaller**bigger)
        ans = ans % MOD
        
print(ans)

### FIXED CODE ###

MOD = 998244353

n = int(input())
distances = list(map(lambda x: int(x), input().split()))

# 最初が0であることを確認
canSolve = True
ans = 1

if distances[0] != 0:
    canSolve = False
    ans = 0

dist_list = {}
if canSolve:
    for i in distances:
        if i in dist_list.keys():
            dist_list[i] += 1
        else:
            dist_list[i] = 1
            
            
    keys = list(dist_list.keys())
    keys.sort()
    keys.reverse()
    bigger = None
    smaller = None
    pre_v = None
    for v in keys:
        if bigger is None:
            bigger = dist_list[v]
            pre_v = v
            continue
        elif smaller is None:
            smaller = dist_list[v]
        else:
            bigger = smaller
            smaller = dist_list[v]
        
        if v==0 and smaller > 1:
            ans = 0

        if v == pre_v - 1:
            ans *= (smaller**bigger)
            ans = ans % MOD
            pre_v = v
        else:
            ans = 0
        
print(ans)