Harryxun/stf_run huggingface dataset:
def main():
    import itertools
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))
    c = tuple(map(int,input().split()))
    d = (a[0],b[0],c[0])
    e = (a[1],b[1],c[1])
    f = (a[2],b[2],c[2])
    g = (a[0],b[1],c[2])
    h = (a[2],b[1],c[0])
    A = set(a)
    B = set(b)
    C = set(c)
    D = set(d)
    E = set(e)
    F = set(f)
    G = set(g)
    H = set(h)
    n = int(input())
    listB = [int(input()) for x in range(n)]
    X = itertools.combinations(listB,3)
    R = set(list(X))
    if A in R or B in R or C in R or D in R or E in R or F in R or G in R or H in R:
      print("Yes")
    else:
      print("No")
main()

### FIXED CODE ###

def main():
    N = int(input())
    if N%2 == 1:
      print(int((N+1)/2))
    else:
      print(int(N/2))
main()
#55 C - Cat Snuke and a Voyage
import collections from deque
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

### FIXED CODE ###

#55 C - Cat Snuke and a Voyage
from collections import deque
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
        
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
import sys
sys.setrecursionlimit(10**8)

A, B = map(int, input().split())

def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    return gcd(a, b%a)

primes = []
for i in range(2, 10**3+10):
    if all(i%p for p in primes):
        primes.append(i)

g = gcd(A, B)
l = [0]*(g+1)
for p in primes:
    if g < p:
        break
    while g%p == 0:
        l[p] = 1
        g //= p
        if g == 1:
            break
    if g == 1:
        break

print(sum(l)+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

A, B = map(int, input().split())

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a%b)

g = gcd(A, B)
count = 0
for i in range(2, 10**6+3):
    if g%i == 0:
        count += 1
    while g%i == 0:
        g //= i
if g != 1:
    count += 1

print(count+1)
a, b, c = map(int,input().split())
if a==b+c or b==a+c or c==a+b:
   print(Yes)
else:print(No)

### FIXED CODE ###

a,b,c = list(map(int,input().split()))
if a==b+c or b==a+c or c==a+b :print('Yes')
else:print('No')
N,M = map(int,input().split())
check = False
a = []
pass_list = [0]*(N+1)
a.append(int(input()))
for i in range(1,M):
    a.append(int(input()))
    
if(1 not in a):
    pass_list[1]=1
if(2 not in a):
    pass_list[2]=1
for i in range(2,N+1):
    if(i not in a):
        pass_list[i] += pass_list[i-1]+pass_list[i-2]
print(pass_list[N]%1000000007)


### FIXED CODE ###

N,M = map(int,input().split())
a = [0]*(N+2)
pass_list = [0]*(N+2)

for i in range(M):
    b = int(input())
    a[b] = 1
if(a[1] !=1):
    pass_list[1]=1
if(a[2] !=1):
    pass_list[2]=1
for i in range(2,N+1):
    if(a[i] != 1):
        pass_list[i] += pass_list[i-1]+pass_list[i-2]
print(pass_list[N]%1000000007)
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,a,b=map(int, input().split())
    if n==1 and a==b:
        print(1)
    elif n==1 and a!=b:
        print(0)
    elif b<a:
        print(0)
    else:
        import itertools
        l=list(range(a,b+1))
        c=itertools.combinations_with_replacement(l,n-2)
        check=[]
        cnt=0
        for i in c:
            if sum(i) not in check:
                check.append(sum(i))
                cnt+=1
        print(cnt)
resolve()

### FIXED CODE ###

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

def resolve():
    import itertools
    n,a,b=map(int, input().split())
    if n==1 and a==b:
        print(1)
    elif n==1 and a!=b:
        print(0)
    elif b<a:
        print(0)
    else:
        print((a+(n-1)*b)-((n-1)*a+b)+1)
resolve()
N=int(input())
import math

#hoge=[[108]]

#x=[3,5,7,11,13,17,19]
#a=[pow(2,3)*i for i in x]

x=[5,7]
b=[[pow(3,3)*i for i in x]]

#x=[5,7,11,13,17,19,23,29,31]
#c=[2*3*i for i in x]

#x=[7,11,13,17,19]
#d=[2*5*i for i in x]

#x=[11,13]
#e=[2*7*i for i in x]

x=[7,11,13]
f=[3*5*i for i in x]

b.append(f)



x=[]
for v in b:
  for item in v:
    x.append(item)


x.sort()
import numpy as np
X=[N-x[i] for i in range(len(x))]
XX=np.where(np.array(X) < 0) 
print(XX[0][0])

### FIXED CODE ###

import numpy as np
N=int(input())
x=[105, 135, 165, 189, 195]

X=[N-x[i] for i in range(len(x))]
XX=np.where(np.array(X) < 0) 
if N<195:
  print(XX[0][0])
else:
  print(5)
import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

l = [1]
while True:
    x = A[l[-1]-1]
    if x in l:
        break
    l.append(x)
print(l[x-1:][k % len(l)])


### FIXED CODE ###

import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(l[l.index(x):])
if len(l) > k:
    print(l[k])
else:
    print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])
import functools
[N,M] = [int(x) for x in input().split()]
XYZ = []
for i in range(N):
  XYZ.append([int(x) for x in input().split()])
result = 0
for x in range(-1, 2, 2):
  for y in range(-1, 2, 2):
    for z in range(-1, 2, 2):
      contribute = [x, y, z]
      score = [functools.reduce(lambda a, b: a + b, [xyz[i] * contribute[i] for i in range(3)]) for xyz in XYZ]
      score.sort(reverse=True)
      result = max(result, functools.reduce(lambda a, b: a + b, score[:M]))
print(result)

### FIXED CODE ###

import functools
[N, M] = [int(x) for x in input().split()]
XYZ = []
for i in range(N):
  XYZ.append([int(x) for x in input().split()])
result = 0
for x in range(-1, 2, 2):
  for y in range(-1, 2, 2):
    for z in range(-1, 2, 2):
      contribute = [x, y, z]
      score = [functools.reduce(lambda a, b: a + b, [xyz[i] * contribute[i] for i in range(3)]) for xyz in XYZ]
      score.sort(reverse=True)
      S = functools.reduce(lambda a, b: a + b, score[:M]) if M else 0
      result = max(result, S)
print(result)
alfa=input()
N=int(alfa[0])
X=int(alfa[2])
#L=[int(input().split()) for i in range(N)]
L=input().split()


print(N,X,L)
D=0
count=0
for i in range(N):
    count+=1
    D+=int(L[i])
    if D>X:
        print(count)
        break


### FIXED CODE ###

alfa=input()

X=alfa[0]
A=alfa[2]

if X<A:
    print("0")
else:
    print("10")
n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(n):
    for j in range(n):
        if i!=j:
            for k in range(j+1,n):
                if a[j]==a[k]:
                    ans[i]+=1
for i in range(n):
    print(ans[n])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=[0]*(n+1)
ans=0
for i in range(n):
    cnt[a[i]]+=1
for j in range(n+1):
    ans+=(cnt[j]*(cnt[j]-1))//2
for k in range(n):
    print(ans-(cnt[a[k]]-1))
n = int(input())
lis = list(map(int, input().split()))
key = lis[0]
num = [0]
li = [key]
for i in range(1,n):
	if lis[i] > key:
		line = lis[i]
		num.append(i)
		li.append(line)
m = len(li)
nu = [li[0]]+[li[i+1]-li[i] for i in range(m-1)]
he = [0]*m
cou = [0]*m
from bisect import bisect_left
for k in lis:
	sen = bisect_left(li,k)
	cou[sen] += k -li[sen]
	he[sen] += 1
t = 0
for i in reversed(range(m)):
	t += he[i]
	he[i] = t
for i in range(m):cou[i] += he[i]*nu[i]
ans = [0]*n
for i,c in zip(num,cou):ans[i] = c
for r in ans:print(r)

### FIXED CODE ###

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

key = lis[0]
num = [0]
li = [key]
for i in range(1,n):
	if lis[i] > key:
		key = lis[i]
		num.append(i)
		li.append(key)

m = len(li)
nu = [li[0]]+[li[i+1]-li[i] for i in range(m-1)]

he = [0]*m
cou = [0]*m

from bisect import bisect_left

for k in lis:
	sen = bisect_left(li,k)
	cou[sen] += k -li[sen]
	he[sen] += 1

key = 0
for i in reversed(range(m)):
	key += he[i]
	he[i] = key

for i in range(m):
	cou[i] += he[i]*nu[i]

ans = [0]*n
for i,c in zip(num,cou):
	ans[i] = c

for r in ans:
	print(r)
n = int(input())
hs = list(map(int, input().split()))

def best(plants, counter):
    all0 = True
    started = False
    for i,p in enumerate(plants):    
        if p > 0:
            all0 = False
        if p == 0:
            if started:
                break
            else:
                continue
        plants[i] -= 1
        started = True
    
    if all0:
        return counter
    return best(plants, counter+1)
    
counter = best(hs, 0)
print(counter)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n = int(input())
hs = list(map(int, input().split()))

def best(plants, counter):
    all0 = True
    started = False
    for i,p in enumerate(plants):    
        if p > 0:
            all0 = False
        if p == 0:
            if started:
                break
            else:
                continue
        plants[i] -= 1
        started = True

    if all0:
        return counter
    return best(plants, counter+1)
    
cnt = best(hs, 0)
print(cnt)
N = int(input())
count = 0

for i in range(N):
  if N <= int(i*1.08) < N+1:
    print(i)
    count += 1

if count == 0:
    print(":(")


### FIXED CODE ###

li = []
for i in range(2):
  a,b = map(int, input().split())
  li.append(a)
  
if li[1] == li[0]+1:
  print(1)
else:
  print(0)
##C
N = int(input())
S = list(input() for i in range(N))

import collections

c = collections.Counter(S)
ans = 0
for j in range(N):
    if c.most_common()[0][1] == c.most_common()[j][1]:
        ans += 1
    else:
        break
ansl = list()
for k in range(ans):
    ansl.append((c.most_common()[k][0]))
ansl.sort()
for l in ansl:
    print(l)

### FIXED CODE ###

N = int(input())
S = list(input() for i in range(N))

import collections

c = collections.Counter(S)
max = max(c.values())
 
max_k_list = [kv[0] for kv in c.items() if kv[1] == max]
max_k_list.sort()
for l in max_k_list:
    print(l)
from collections import defaultdict
mod = 10**9+7
N = int(input())
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

def dfs(i,j):
    if d[(i,j)]!=-1:
        return d[(i,j)]
    res = 1
    for k in g[j]:
        if k==i:
            continue
        res += dfs(j,k)
    d[(i,j)] = res
    return res
dfs(a,b)
dfs(b,a)

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

print(ans)

### FIXED CODE ###

from collections import defaultdict,deque
mod = 10**9+7
N = int(input())
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = deque([[a,b]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

q = deque([[b,a]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

print(ans)
S=list(int(input()))
s=0
i=0
if S[i]==S{i+1]==0 or S[i]==S[i+1]==1:
  s=s
  i+=1
else:
  s+=2
  del S[i:i+2]
  i=0
print(s)

### FIXED CODE ###

S=input()
N=len(S)
a=S.count('0')
b=S.count('1')
t=min(a,b)
print(2*t)
a, b, k = map(int, input().split())
if k <= a:
    a1 = a - k
elif a < k and k < a + b:
    a1 = 0
    b1 = b - (k-a)
else:
    a1 = 0
    b1 = 0

print(a1, b1)

### FIXED CODE ###

a, b, k = map(int, input().split())
if k <= a:
    a1 = a - k
    b1 = b
elif a < k and k < a + b:
    a1 = 0
    b1 = b - (k-a)
else:
    a1 = 0
    b1 = 0

print(a1, b1)
def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
if Base_10_to_n(int(input()), 9)[-1] == '0':
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
if N % 9 == 0:
    print('Yes')
else:
    print('No')
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp_[j - w] + v:
                    dp_[j] = dp_[j - w] + v
            dp.append(dp_)
            V.append(v)
            W.append(w)
        else:
            V.append(v)
            W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            cnt = 0
            v_ = []
            w_ = []
            while v > m:
                v_.append(V[v-1])
                w_.append(W[v-1])
                v >>= 1
                cnt += 1
            ret = dp[v][L]
            v_tmp = [0] * (1 << cnt)
            w_tmp = [0] * (1 << cnt)
            for b in range(1, 1 << cnt):
                lsb = b & -b
                l = lsb.bit_length()
                w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()
N, K =map(int, input().split())
lst = []
for _ in range(N):
    lst.append(int(input()))
sor = sorted(lst)

mindiff = float('inf')
for i in range(N-K+1):
    diff = selected[i] - selected[i+K-1]
    if diff <= mindiff:
        mindiff = diff
print(mindiff)

### FIXED CODE ###

N, K =map(int, input().split())
lst = []
for _ in range(N):
    lst.append(int(input()))
sor = sorted(lst)

mindiff = float('inf')
for i in range(N-K+1):
    diff = sor[i+K-1] - sor[i] 
    if diff <= mindiff:
        mindiff = diff
print(mindiff)
H, W = map(int, input().split())
S = [[] for _ in range(H)]
for i in range(H):
    S[i] = list(input())

count = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            count[i][j] = 10**7
        else:
            count[i][j] = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            if j != W-1 and S[i][j+1] == '#':
                count[i][j] += 1
            if j != 0 and S[i][j-1] == '#':
                count[i][j] += 1
            if i != W-1 and S[i+1][j] == '#':
                count[i][j] += 1
            if i != 0 and S[i-1][j] == '#':
                count[i][j] += 1

check = 0
for i in range(H):
    for j in range(W):
        if count[i][j] < 1:
            check = 1

if check == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

H, W = map(int, input().split())
S = [[] for _ in range(H)]
for i in range(H):
    S[i] = list(input())

count = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            count[i][j] = 10**7
        else:
            count[i][j] = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            if j != W-1: 
                if S[i][j+1] == '#':
                    count[i][j] += 1
            if j != 0: 
                if S[i][j-1] == '#':
                    count[i][j] += 1
            if i != H-1: 
                if S[i+1][j] == '#':
                    count[i][j] += 1
            if i != 0: 
                if S[i-1][j] == '#':
                    count[i][j] += 1

check = 0
for i in range(H):
    for j in range(W):
        if count[i][j] < 1:
            check = 1

if check == 0:
    print('Yes')
else:
    print('No')
n = int(input())
a = list(map(int, input().split()))
ans = [0 for in range(n)
for i in range(n):
       ans[a[i]-1] = i+1
for j in range(len(ans):
       print(ans[i] , end = " ")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
       ans[a[i]-1] = i+1
for j in range(len(ans)):
       print(ans[j] , end = " ")
n = int(input())
a = [int(input()) for i in range(n-1)]

for i in (reversed(a)):
    print(i)


### FIXED CODE ###

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

print(' '.join(map(str, reversed(a))))
a,b,x = map(int,input().split())

if a > x or b < x:
    print("0")
elif a%x == 0:
    print(b//x-a//x+1)
else:
    print(b//x-a//x)




### FIXED CODE ###

a,b,c = input().split()

print(a[0]+b[0]+c[0])
n=int(input())
if len(n)==1:
    print(n)
elif len(n)==2:
    print(9)
elif len(n)==3:
    print(n-90)
elif len(n)==4:
    print('909')
elif len(n)==5:
    print(n-9090)
else:
    print('90909')

### FIXED CODE ###

n=input()
if len(n)==1:
    print(n)
elif len(n)==2:
    print('9')
elif len(n)==3:
    print(int(n)-90)
elif len(n)==4:
    print('909')
elif len(n)==5:
    print(int(n)-9090)
else:
    print('90909')
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

def dfs(u, c):
    color[u] = c
    for v in graph[u]:
        if color[v] == c:
            return False
        if color[v] == 0 and not dfs(v, -c):
            return False
        
    return True

graph = [[] for _ in range(N)]
for a, b in X:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

color = [0] * N
if dfs(0, 1):
    c = sum(v == 1 for v in color)
    print(c * (N - c) - M)
else:
    print(N * (N - 1) // 2 - M)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]
for x, y in edges:
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)

def dfs(v, c):
    # c: color = 1 or -1
    node[v] = c
    for i in graph[v]:
        if node[i] == c:
            return False
        
        if node[i] == 0 and not dfs(i, -c):
            return False
        
    return True

node = [0] * N
if dfs(0, 1):
    x = sum(v + 1 for v in node) // 2
    print(x * (N - x) - M)
else:
    print(N * (N - 1) // 2 - M)
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())
D = list(map(int, input().split()))
MOD = 998244353
cnt = [0] * (10 ** 5 + 1)
for d in D:
    cnt[d] += 1

if cnt[0] != 1:
    print(0)
    exit()
ans = cnt[0]
for i in range(1, dmax + 1):
    if cnt[i] == 0:
        print(0)
        exit()
    now = my_pow(cnt[i - 1], cnt[i], MOD)
    ans *= now
    ans %= MOD
print(ans)


### FIXED CODE ###

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())
D = list(map(int, input().split()))
dmax = max(D)
MOD = 998244353
cnt = [0] * (10 ** 5 + 1)
for d in D:
    cnt[d] += 1

if D[0] or cnt[0] != 1:
    print(0)
    exit()
ans = cnt[0]
for i in range(1, dmax + 1):
    now = my_pow(cnt[i - 1], cnt[i], MOD)
    ans *= now
    ans %= MOD
print(ans)
n=int(input())
s=input()
l=[]
for i in s:
    l.append(i)
#print(l)
count=0
for i in range(len(l)):
    if l[i]=="A" and l[i+1]=="B" and l[i+2]=="C":
            count+=1
print(count)

### FIXED CODE ###

n=int(input())
s=input()
l=[]
for i in s:
    l.append(i)
#print(l)
count=0
for i in range(len(l)-2):
    if l[i]=="A" and l[i+1]=="B" and l[i+2]=="C":
            count+=1
print(count)
w,h,n=map(int,input().split())
A=[[0 for i in range(w)] for j in range(h)]
for i in range(n):
  a,b,c=map(int,input().split())
  if c==1:
    for i in range(h):
      for j in range(a):
        A[i][j]=1
  elif c==2:
    for i in range(h):
      for j in range(w-a):
        A[i][j+a]=1
  elif c==3:
    for i in range(b):
      A[i]=[1 for i in range(w)]
  else:
    for i in range(h-b):
      A[h-i]=[1 for i in range(w)]
ans=0
for i in range(h):
  ans+=A[i].count(0)
print(ans)

### FIXED CODE ###

w,h,n=map(int,input().split())
A=[[0 for i in range(w)] for j in range(h)]
for i in range(n):
  a,b,c=map(int,input().split())
  if c==1:
    for i in range(h):
      for j in range(a):
        A[i][j]=1
  elif c==2:
    for i in range(h):
      for j in range(w-a):
        A[i][j+a]=1
  elif c==3:
    for i in range(b):
      A[i]=[1 for i in range(w)]
  else:
    for i in range(h-b):
      A[h-i-1]=[1 for i in range(w)]
ans=0
for i in range(h):
  ans+=A[i].count(0)
print(ans)