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

# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

def check(r, g, k):
    return +(r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N):
    cur = que[k]
    nxt = que[k+1]
    for r, g in cur:
        # r < g < b < k+1 の関係を元に次の状態に伝播

        # 制約を満たす場合のみに伝播
        if check(g, k, k+1):
            nxt[g, k] = (nxt.get((g, k), 0) + cur[r, g]) % MOD
        if check(r, k, k+1):
            nxt[r, k] = (nxt.get((r, k), 0) + cur[r, g]) % MOD
        if check(r, g, k+1):
            nxt[r, g] = (nxt.get((r, g), 0) + cur[r, g]) % MOD
print(sum(que[N].values()) % MOD)


### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
sr -= 1
sc -= 1

s = input()
t = input()

d = {
    'L': (0, -1),
    'R': (0, 1),
    'U': (-1, 0),
    'D': (1, 0)
}


def next_move_pos(cur_r, cur_c, cur_step_index, bl_is_takahashi):
    if bl_is_takahashi:
        c = s[cur_step_index]
    else:
        c = t[cur_step_index]
    dr, dc = d[c]
    return cur_r + dr, cur_c + dc


def is_in_range(r, c):
    return 0 <= r < H and 0 <= c < W


def rec(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi):
    if bl_cur_player_takahashi:
        nr, nc = next_move_pos(cur_r, cur_c, cur_step_index, True)
        if not is_in_range(nr, nc):
            return True
        if rec(nr, nc, cur_step_index, not bl_cur_player_takahashi):
            return True
        if rec(cur_r, cur_c, cur_step_index, not bl_cur_player_takahashi):
            return True
    else:
        if cur_step_index == N - 1:
            return False
        for nr, nc in (cur_r, cur_c), next_move_pos(cur_r, cur_c, cur_step_index, False):
            if not is_in_range(nr, nc): continue
            nnr, nnc = next_move_pos(nr, nc, cur_step_index + 1, True)
            if not is_in_range(nnr, nnc): continue
            if not rec(nr, nc, cur_step_index + 1, not bl_cur_player_takahashi):
                return False
            if not rec(cur_r, cur_c, cur_step_index + 1, not bl_cur_player_takahashi):
                return False
        return True


print('NO' if rec(sr, sc, 0, True) else 'YES')


### FIXED CODE ###

def main():
    h, w, n = map(int, input().split())
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    s, t = input(), input()

    u, d, l, r = 0, h - 1, 0, w - 1

    for ss, tt in reversed(tuple(zip(s, t))):
        if tt == 'U': d = min(d + 1, h - 1)
        if tt == 'D': u = max(u - 1, 0)
        if tt == 'L': r = min(r + 1, w - 1)
        if tt == 'R': l = max(l - 1, 0)

        if ss == 'U': u += 1
        if ss == 'D': d -= 1
        if ss == 'L': l += 1
        if ss == 'R': r -= 1

        if l > r or u > d:
            print('NO')
            return

    if l <= x <= r and u <= y <= d:
        print('YES')
        return
    else:
        print('NO')
        return


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

n=int(input())

a=list(map(int,input().split()))
b=[a[0]]
if n%2:#n%2==1
    for i in range(1,n):
        if i%2==1:
            b.append(a[i])
        else:
            b.insert(0,a[i])
else:
    for i in range(1,n):
        if i%2==0:
            b.append(a[i])
        else:
            b.insert(0,a[i])
"""
for i in range(n):
    b.append(a[i])
    b.reverse()
"""
for i in range(n):
    print(b[i],end=" ")

### FIXED CODE ###

n=int(input())

a=list(map(int,input().split()))
b=[0]*n
cen=n//2
if n%2:#n%2==1
    for i in range(0,n):
        if i%2==1:
            b[cen+(i+1)//2]=a[i]
        else:
            b[cen-(i+1)//2]=a[i]
else:
    for i in range(0,n):
        if i%2==1:
            b[cen-(i+1)//2]=a[i]
        else:
            b[cen+(i+1)//2]=a[i]
"""
for i in range(n):
    b.append(a[i])
    b.reverse()
"""
for i in range(n):
    print(b[i],end=" ")
### BUGGY CODE ###

try:
	while True:
		limit = input()
		ans = [2]
		for i in range(3, limit + 1, 2):
			k = 0
			while len(ans) != k:
				if i % ans[k] == 0:
					break
				else:
					if len(ans) == k + 1:
						ans.append(i)
				k = k + 1
				print len(ans)
		print len(ans)
except EOFError:
	pass

### FIXED CODE ###

def prime_count(n):
	j = 0
	ans = [1] * (n + 1)
	ans[0] = ans[1] = 0
	for i in xrange(3, n + 1, 2):
		if i * 2 > n:
			break
		if ans[i] != 0:
			for j in xrange(2 * i, n + 1, i):
				ans[j] = 0
	for k in xrange(2 * 2, n + 1, 2):
		ans[k] = 0
	print sum(ans)

try:
	while True:
		n = input()
		prime_count(n)
except EOFError:
	pass
### BUGGY CODE ###



def read_input():
    n = int(input())
    xlist = list(map(int, input().split()))
    return n, xlist


def get_median(s):
    l = len(s)
    return s[int((l-1)/2)]


def submit():
    n, xlist = read_input()

    xlist = [(x, i) for i, x in enumerate(xlist)]
    xlist.sort(key=lambda x: x[0])

    pos_dic = {}
    for i, x in enumerate(xlist):
        pos_dic[x[1]] = i

    for i in range(n):
        target = pos_dic[i]
        p = xlist.pop(target)
        print(get_median(xlist)[0])
        xlist.insert(target, p)




if __name__ == '__main__':
    submit()


### FIXED CODE ###



def read_input():
    n = int(input())
    xlist = list(map(int, input().split()))
    return n, xlist


def get_median(s, ignore):
    l = len(s)
    if ignore < l/2:
        return s[int((l+1)/2)]
    else:
        return s[int((l-1)/2)]

def submit():
    n, xlist = read_input()

    xlist = [(x, i) for i, x in enumerate(xlist)]
    xlist.sort(key=lambda x: x[0])

    pos_dic = {}
    for i, x in enumerate(xlist):
        pos_dic[x[1]] = i

    for i in range(n):
        target = pos_dic[i]
        print(get_median(xlist, target)[0])




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

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0
for i in range(n):
  for j in range(i+1,min(i+k+1,n)):
    d=dp[i]+abs(h[i]-h[j])
    if d<dp[j]:
      dp[j]=d
print(dp[n-1])      
      
      
  

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0
for i in range(n):
  for j in range(i+1,min(i+k+1,n)):
    d=dp[i]+abs(h[i]-h[j])
    if d<dp[j]:
      dp[j]=d
print(dp[n-1])
### BUGGY CODE ###

N = int(input().strip())
A = list(map(int,input().strip().split(' ')))
B = list(map(int,input().strip().split(' ')))
C = list(map(int,input().strip().split(' ')))
A.sort()
B.sort()
C.sort()
bstart = 0
cstart = 0
ans = 0
for ai in range(N):
    a = A[ai]
    cstart = 0
    for bi in range(bstart,N):
        b = B[bi]
        if a >= b:
            bstart = bi + 1
        else:    
            for ci in range(cstart,N):
                c = C[ci]
                if b >= c:
                    cstart = ci + 1
                else:
                    ans = ans + 1
                    
print(ans)
    

### FIXED CODE ###

import bisect as bi

N = int(input().strip())
A = list(map(int,input().strip().split(' ')))
B = list(map(int,input().strip().split(' ')))
C = list(map(int,input().strip().split(' ')))

A.sort()
B.sort()
C.sort()
ans = 0

for b in B:
    i = bi.bisect_left(A, b) # A[0],...,A[i - 1] < b
    k = bi.bisect_right(C, b) # b < C[k],...C[N-1]
    ans += i * (N - k)

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

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


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

INTMAX = 9223372036854775807
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,K=LI()
INL=LI()
dp = [INTMAX]*N
dp[0] = 0

for i in range(0,N):
    for j in range(1,K+1):
        k = i+j
        if k < N:
            dp[k] = min(dp[k], dp[i]+abs(INL[k]-INL[i]))

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


### FIXED CODE ###

INTMAX = 9223372036854775807
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,K=LI()
INL=LI()
dp = [INTMAX]*N
dp[0] = 0

for i in range(0,N):
    for j in range(1,K+1):
        k = i+j
        if k < N:
            dp[k] = min(dp[k], dp[i]+abs(INL[k]-INL[i]))

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

import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,u,v=LI()

TR=[[] for i in range(N+1)]
for _ in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

DIST=[(-1,-1) for i in range(N+1)]
DIST[v] = (0, -1)
def dfs(root=v):
    maxdist = DIST[root][0]
    for vtx in TR[root]:
        if DIST[vtx][0] == -1:
            DIST[vtx] = (DIST[root][0] + 1, -1)
            maxdist = max(maxdist, dfs(vtx))
    DIST[root] = (DIST[root][0], maxdist)
    return maxdist

DIST2=[(-1,-1) for i in range(N+1)]
LST = 0
def dfs2(root=u):
    global LST
    maxdist = DIST2[root][0]
    for vtx in TR[root]:
        if DIST2[vtx][0] == -1 and DIST2[root][0] + 1 < DIST[vtx][0]:
            LST = max(LST, DIST[vtx][0])
            DIST2[vtx] = (DIST2[root][0] + 1, -1)
            maxdist = max(maxdist, dfs2(vtx))
    DIST2[root] = (DIST2[root][0], maxdist)
    return maxdist

dfs()
dfs2()
# print(DIST)
# print(DIST2)

print(max(0, LST-1))


### FIXED CODE ###

import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,u,v=LI()

TR=[[] for i in range(N+1)]
for _ in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

DIST1=[-1]*(N+1)
DIST2=[-1]*(N+1)
FIFO = deque()

FIFO.append((v,0))
while FIFO:
    edge, dist = FIFO.popleft()
    DIST1[edge] = dist
    for i in TR[edge]:
        if DIST1[i] == -1:
            FIFO.append((i, dist+1))

FIFO.append((u, 0))

farest = 0
while FIFO:
    edge, dist = FIFO.popleft()
    DIST2[edge] = dist
    farest = max(farest, DIST1[edge])
    for i in TR[edge]:
        if DIST2[i] == -1 and dist+1 < DIST1[i]:
            FIFO.append((i, dist+1))

# print(DIST1)
# print(DIST2)
print(max(0, farest-1))
### BUGGY CODE ###

import re
n, q = map(int, input().split(' '))
s = input()
l_r = []
for _ in range(q):
    l_r.append(tuple(map(int, input().split(' '))))
for (l, r) in l_r:
    agct_substr = re.findall(r'AC', s[l-1:r])
    print(len(agct_substr))

### FIXED CODE ###

n, q = map(int, input().split(' '))
s = input()
l_r = []
for _ in range(q):
    l_r.append(tuple(map(int, input().split(' '))))

n = [0]
c = 0
for i in range(1, len(s)):
    if s[i-1:i+1] == 'AC':
        c += 1
    n.append(c)

for (l, r) in l_r:
    print(n[r - 1] - n[l - 1])
### BUGGY CODE ###

MAX = 1000000000


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

dp = [[-1 for j in range(MAX + 1)] for i in range(n)]
dp[0][0] = 1000
for k in range(1, MAX + 1):
    if 1000 - a[0] * k < 0:
        break
    dp[0][k] = 1000 - a[0] * k
print(dp[0])
for i in range(1, n):
    for j in range(MAX + 1):
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        # 買うとき
        for k in range(1, MAX + 1):
            if j - k < 0:
                break
            # if dp[i - 1][j - k] - a[i] * k < 0:
            #     break
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k] - a[i] * k)
        # 売る時
        for k in range(1, MAX + 1):
            if j + k >= MAX + 1:
                break
            if dp[i - 1][j + k] < 0:
                break
            dp[i][j] = max(dp[i][j], dp[i - 1][j + k] + a[i] * k)
    print(dp[i])
ans = max(dp[-1])
print(max(ans, 1000))
    # return max(ans, 1000)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = []
flag = True
for i in reversed(range(n)):
    if i == 0:
        if not flag:
            x.append(a[i])
        break
    flag2 = flag
    if flag:
        if a[i - 1] < a[i]:
            x.append(a[i])
            flag2 = not flag2
    else:
        if a[i - 1] > a[i]:
            x.append(a[i])
            flag2 = not flag2
    flag = flag2
x = x[::-1]
m = len(x)
if m % 2 == 1:
    x = x[1:]
# print("x =", x)
cur_money = 1000
cur_stock = 0
for i in range(m):
    if i % 2 == 0:
        cur_stock += cur_money // x[i]
        cur_money %= x[i]
    else:
        cur_money += x[i] * cur_stock
        cur_stock = 0
print(cur_money)
### BUGGY CODE ###

n = int(input())
ans=0
for i in range(n):
    ans+=i
print(ans)

### FIXED CODE ###

n = int(input())
print(round(n*(n-1)//2))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from itertools import chain
H,W = (int(x) for x in input().split())
S = [list(input()) for _ in range(H)]
mem = [[[0,0] for _ in range(W)] for _ in range(H)]
ans = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            h = mem[i][j][0]
            if h == 0:
                stopped = False
                for k in range(W-j-1):
                    if S[i][j+k+1] == '#':
                        for l in range(k+1):
                            mem[i][j+l][0] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(W-j):
                        mem[i][j+l][0] = W-j
                h = mem[i][j][0]
            v = mem[i][j][1]
            if v == 0:
                stopped = False
                for k in range(H-i-1):
                    if S[i+k+1][j] == '#':
                        for l in range(k+1):
                            mem[i+l][j][1] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(H-i):
                        mem[i+l][j][1] = H-i
                v = mem[i][j][1]
            ans[i][j] = h + v - 1
print(max(chain(*ans)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W = (int(x) for x in input().split())
S = [list(input()) for _ in range(H)]
memh = [[0] * W for _ in range(H)]
memv = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            h = memh[i][j]
            if h == 0:
                stopped = False
                for k in range(W-j-1):
                    if S[i][j+k+1] == '#':
                        for l in range(k+1):
                            memh[i][j+l] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(W-j):
                        memh[i][j+l] = W-j
                h = memh[i][j]
            v = memv[i][j]
            if v == 0:
                stopped = False
                for k in range(H-i-1):
                    if S[i+k+1][j] == '#':
                        for l in range(k+1):
                            memv[i+l][j] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(H-i):
                        memv[i+l][j] = H-i
                v = memv[i][j]
            ans = max(ans,h+v-1)
print(ans)
### BUGGY CODE ###

import math
k = int(input()) + 1
total = 0

for i in range(1,k):
    for j in range(1,k):
        for l in range(1,k):
            total += math.gcd(i, math.gcd(j,l))

print(total)

### FIXED CODE ###

from math import gcd
k = int(input())
total = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            total += gcd(gcd(i,j),l)

print(total)
### BUGGY CODE ###

from collections import Counter
N = int(input())
li = list(map(int, input().split()))
for k in range(N):
    check_li, ans = li[:k]+li[k+1:], 0
    counter = Counter(check_li)
    for i in counter.most_common():
        cnt = i[1]
        ans += cnt * (cnt-1)
    print(ans//2)

### FIXED CODE ###

from collections import Counter
N, li = int(input()), list(map(int, input().split()))
cnt_dict, cnt_total = Counter(li), 0
for i in cnt_dict.items():
    cnt_total += i[1] * (i[1]-1) // 2
for k in range(N):
    buf = cnt_dict[li[k]]
    print(cnt_total - buf*(buf-1)//2 + (buf-1)*(buf-2)//2)
### BUGGY CODE ###

s=input()
K=int(input())
substring=set()
for start in range(len(s)):
    for end in range(start+1,len(s)+1):
        substring.add(s[start:end])
print(sorted(list(substring))[K-1])

### FIXED CODE ###

s=input()
K=int(input())
substring=set()
for start in range(len(s)):
    for end in range(start+1,min(len(s)+1,start+K+1)):
        substring.add(s[start:end])
print(sorted(list(substring))[K-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
G=[[] for i in range(n+1)]
flag=[1]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    G[x].append(y)
    flag[y]=0
# dp[i] node iからの最長パス
dp=[-1]*(n+1)
st=[]
for i in range(1,n+1):
    if flag[i]:
        st.append(i)
ans=0

def dfs(x):
    max_kyori=0
    dist=[-1]*(n+1)
    dist[x]=0
    stack=[x]
    while stack:
        a=stack.pop()
        kyori = dist[a]
        if G[a]!=[]:
            for t in G[a]:
                dist[t]=kyori+1
                max_kyori=max(max_kyori,kyori+1)
                stack.append(t)
    return max_kyori
kotae=0
for i in st:
    kotae=max(kotae,dfs(i))
print(kotae)

### FIXED CODE ###

import sys
input = sys.stdin.readline
#bfsするからdequeじゃないとだめ
from collections import deque
n,m=map(int,input().split())
infi=10**10
#topological sort
#通常のグラフ構成のグラフ
graph1=[[]for _ in range(n+1)]
#入ってくる辺の数を記録するグラフ
graph2=[ 0 for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    graph1[x].append(y)
    graph2[y]+=1
#start地点になるのは入ってくる辺の数が0の点
start=deque([])
for i in range(1,n+1):
    if graph2[i]==0:
        start.append(i)
#start地点から
#①topoリストに加える
#②隣接点の入ってくる辺の数を減らす
#③入ってくる辺の数が0になったらstartに加える
#を繰り返す
#※今回はtopoに加えるのは本質ではない。
#topoに加えていく順序で見ていきながら距離を入れていく。
# topo=[]
dist=[infi]*(n+1)
for i in start:
    dist[i]=0
while start:
    a=start.popleft()
    kyori=dist[a]
#     topo.append(a)
    for b in graph1[a]:
        graph2[b]-=1
        if graph2[b]==0:
            start.append(b)
            dist[b]=min(dist[b],dist[a]+1)
print(max(dist[1:]))
### BUGGY CODE ###

s = input()
k = int(input())
sub = set()
flag = False
for i in range(len(s)):
    for j in range(len(s) - i):
        sub.add(s[j:j + i + 1])
print(sorted(list(sub))[k - 1])

### FIXED CODE ###

s = input()
k = int(input())
sub = set()
for i in range(len(s)):
    for j in range(i, i + k + 1):
        sub.add(s[i:j])
print(sorted(list(sub))[k])
### BUGGY CODE ###

n = input()
A = map( int , raw_input().split() )
q = input()
mi = map( int , raw_input().split() )

def solve(i, m):
  if m == 0:
    return True
  elif i >= n:
    return False
  else:
    res = solve( i+1 , m ) | solve( i+1 , m-A[i] )
    return res

for m in mi:
  if solve( 0 , m ): print "yes"
  else: print "no"
   

### FIXED CODE ###

n = input()
A = map( int , raw_input().split() )
q = input()
mi = map( int , raw_input().split() )

def solve(i, m):
  if m == 0:
    return True
  elif i >= n or m > sum(A):
    return False

  res = solve( i+1 , m ) or solve( i+1 , m-A[i] )
  return res

for m in mi:
  if solve( 0 , m ): print "yes"
  else: print "no"
### BUGGY CODE ###

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  a,b = [int(s) for s in input().split()]
  lst=lst+[[a,b,a*b]]
lst.sort()
m=0
i=0
cost=0
while(m<M):
  m+=lst[i][1]
  cost+=lst[i][2]
  i+=1
if(m>M):
  cost-=lst[i-1][0]*(m-M)
print(cost)

### FIXED CODE ###

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(A, B + 1):
    if abs(A - i) < K or abs(B - i) < K:
        print(i)


### FIXED CODE ###

A, B, K = map(int, input().split())
if B - A <= 2 * K-1:
    for i in range(A, B + 1):
        print(i)
else:
    for i in range(A, A + K):
        print(i)
    for i in range(B - K + 1, B + 1):
        print(i)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
c=[0]*(n+1)
ans=1
for i in range(0,n):
  c[d[i]]+=1

if d[0]!=0 or c[0]!=1:
  print(0)
  
else:
  for j in range(1,n):
    if ans==0:
      break
    elif c[j]==0 and c[j+1]==0:
      ans+=0
    else:
      ans*=c[j-1]**c[j]
      
  print(ans%998244353)  
    
  



### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
x=max(d)
li=[0]*(x+1)
for i in range(n):
    li[d[i]]+=1
if d[0]!=0 or li[0]!=1:
    print(0) 
else:
    ans=1
    for i in range(2,len(li)):
        ans*=pow(li[i-1],li[i],998244353)   
    print(ans%998244353)