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

from numba import jit

@jit
def main():
  N=int(input())
  S=list(map(int,input().split()))
  count=0
  P=[0]*(N*N+1)
  for j in range(N*N):
    P[S[j]]=j+1
  d=[-1]*(N*N+1)
  for i in range(N*N):
    player=S[i]
    hayasa=P[player]

    que=[[] for _ in range(N)]
    que[0].append(player)
    d[player]=i

    j=0
    finish=0
    while True:
      for kouho in que[j]:
        if kouho%N==0:
          finish=1
          break
        if kouho%N==1:
          finish=1
          break
        if kouho+N>N*N:
          finish=1
          break
        if kouho<N:
          finish=1
          break

        if d[kouho+N]<i:
          if P[kouho+N]>hayasa:
            que[j+1].append(kouho+N)
            d[kouho+N]=i
          else:
            que[j].append(kouho+N)
            d[kouho+N]=i

        if d[kouho-N]<i:
          if P[kouho-N]>hayasa:
            que[j+1].append(kouho-N)
            d[kouho-N]=i
          else:
            que[j].append(kouho-N)
            d[kouho-N]=i

        if d[kouho+1]<i:
          if P[kouho+1]>hayasa:
            que[j+1].append(kouho+1)
            d[kouho+1]=i
          else:
            que[j].append(kouho+1)
            d[kouho+1]=i

        if d[kouho-1]<i:
          if P[kouho-1]>hayasa:
            que[j+1].append(kouho-1)
            d[kouho-1]=i
          else:
            que[j].append(kouho-1)
            d[kouho-1]=i
      if finish==1:
        count+=j
        break
      j+=1    
  print(count)

main()

### FIXED CODE ###

from numba import njit
import numpy as np

@njit
def main(N, P):
    lista = [1, -1, N, -N]
    d = np.zeros((N, N), dtype=np.int32)
    d = d.ravel()
    sit = np.ones_like(d)
    stack = np.empty_like(d)
    count = 0
    for i in range(N*N):
        d[i] = min(i % N, (N-1-i) % N, i//N, N-1-i//N)
    for player in P:
        sit[player-1] = 0
        count += d[player-1]
        stack[0] = player
        num = 0
        while num >= 0:
            p = stack[num]
            num -= 1
            a = d[p-1]+sit[p-1]
            for i in lista:
                if p+i < 1 or p + i > N*N:
                    continue
                if d[p+i-1] > a:
                    d[p+i-1] = a
                    num += 1
                    stack[num] = p+i
    print(count)

N = int(input())
P = np.array(input().split(), np.int32)

main(N, P)
### BUGGY CODE ###

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

for i in range(n):
  b.append(a.pop(0))
  b = b[::-1]

print(' '.join(map(str, b)))

### FIXED CODE ###

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

a_even = [elm_a for i, elm_a in enumerate(a) if i % 2 == 0]
a_odd = [elm_a for i, elm_a in enumerate(a) if i % 2 == 1]

ans = a_even[::-1] + a_odd
if n % 2 == 0:
  ans = ans[::-1]

print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

ans=0
B=[0]
for i in range(N):
    B.append(B[i]+A[i])

for k in range(N):
    for j in range(k+1,N+1):
        if B[j]-B[k]==0:
            ans+=1

print(ans)

### FIXED CODE ###

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

ans=0
B=[0]
for i in range(N):
    B.append(B[i]+A[i])

import collections
dic=dict(collections.Counter(B))

C=list(dic.values())

for k in C:
    if k >=2:
        ans += k*(k-1) // 2

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

def resolve():
    from copy import deepcopy
    N = int(input())
    A = list(map(int, input().split()))
    mA = 0
    for i in range(N):
        if mA < A[i]:
            mA = A[i]
    n = 2
    c = 1
    tA = deepcopy(A)
    while sum(A) > N:
        flag = False
        for i in range(N):
            if A[i] % n == 0:
                A[i] = A[i] // n
                flag = True
        if flag:
            c *= n
        else:
            n += 1
    b = 0
    for i in range(N):
        b += c // tA[i]
    print(b % (10**9+7))
resolve()

### FIXED CODE ###

def resolve():
    import fractions
    n=int(input())
    a=[int(i) for i in input().split()]
    g=1
    dx=fractions.gcd
    for i in a:
        g*=i//dx(g,i)
    suml=0
    mod=10**9+7
    for i in a:
        suml+=g*pow(i,mod-2,mod)
        suml%=mod
    print(suml)
resolve()
### BUGGY CODE ###

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

print(ans)

### FIXED CODE ###

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

n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        if(tmpr<0):
            continue
        dp[i]+=accum[tmpr]-accum[tmpl-1]
    accum[i]=dp[i]+accum[i-1]
print(dp[n]%998244353)

### FIXED CODE ###

n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        if(tmpr<0):
            continue
        dp[i]+=accum[tmpr]-accum[tmpl-1]
        dp[i]%=998244353
    accum[i]=dp[i]+accum[i-1]
    accum[i]%=998244353
print(dp[n]%998244353)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

if k - q > 0:
  res = ['Yes'] * n
else:
  res = ['No'] * n
  ans = tuple(set(a))
  for i in ans:
    if k - q + a.count(i) > 0:
      res[i-1] = 'Yes'
print('\n'.join(map(str, res)))

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

if k - q > 0:
  res = ['Yes'] * n
else:
  res = ['No'] * n
  ans = [0] * n
  for i in range(len(a)):
    ans[a[i]-1] += 1
  for i in range(n):
    if k - q + ans[i] > 0:
      res[i] = 'Yes'
print('\n'.join(map(str, res)))
### BUGGY CODE ###

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

INFTY = 1000000001
cnt = [0]

def merge(left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1+1)]
    R = [0 for _ in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = INFTY
    R[n2] = INFTY
    i = 0
    j = 0
    for k in range(left, right):
        cnt[0] += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)
print(" ".join(map(str, A)))
print(cnt[0])


### FIXED CODE ###

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

INFTY = 1000000001
cnt = [0]

def merge(left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    L.append(INFTY)
    R.append(INFTY)
    i = 0
    j = 0
    for k in range(left, right):
        cnt[0] += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)
print(" ".join(map(str, A)))
print(cnt[0])
### BUGGY CODE ###

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

cnt=[0]*60
p=10**9+7
for m in a:
    #b=bin(m)
    #l=len(b)-2
    #print(b)
    for i in range(60):
        if((m>>i) & 1):
            cnt[i]+=1
    #for i in range(l):
    #    cnt[i]+=int(b[-i-1])
    #kei=m
    #for i in range(100):
    #    cnt[i]+=kei%2
    #    kei//=2
    #    if(kei==0):
    #        break

#print(cnt)

lis=[]
jou=1
for i in range(60):
    lis.append(jou)
    jou*=2
    jou%=p

ans=0

for i in range(60):
    ans+=(lis[i]%p)*(cnt[i]%p)*((n-cnt[i])%p)
    ans%=p

print(ans)


### FIXED CODE ###

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

cnt=[0]*60
p=10**9+7
for m in a:
    #b=bin(m)
    #l=len(b)-2
    #print(b)
    for i in range(60):
        if((m>>i) & 1):
            cnt[i]+=1
    #for i in range(l):
    #    cnt[i]+=int(b[-i-1])
    #kei=m
    #for i in range(100):
    #    cnt[i]+=kei%2
    #    kei//=2
    #    if(kei==0):
    #        break

#print(cnt)

lis=[]
jou=1
for i in range(60):
    lis.append(jou)
    jou*=2
    jou%=p

ans=0

for i in range(60):
    ans+=(lis[i]%p)*(cnt[i]%p)*((n-cnt[i])%p)
    ans%=p

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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            yakusu.append(i)
            if n // i != i:
                yakusu.append(n//i)
    return yakusu
     
def main():
    N = I()
    A = LI()
    s = collections.Counter(A)
    cnt = 0
    for a in A:
        flag = True
        for y in yakusu(a):
            if y == a and s[y] == 1:
                continue
            if y in s:
                flag = False
                break
        if flag:
            cnt += 1
    print(cnt)



main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            yakusu.append(i)
            if n // i != i:
                yakusu.append(n//i)
    return yakusu
     
baisu = [False] * (10**6 + 1)
def main():
    N = I()
    A = LI()

    ok = 0
    for a in set(A):
        if baisu[a]:
            continue
        if not baisu[a]:
            num = a + a
            while num < 10**6+1:
                baisu[num] = True
                num += a
    s = collections.Counter(A)
    for a in A:
        if not baisu[a]:
            if s[a] > 1:
                continue
            ok += 1
    print(ok)
main()
### BUGGY CODE ###

I=lambda:tuple(map(int,input().split()));x,y,z,k=I();s=lambda a,b:sorted(i+j for i in a for j in b)[:-k-1:-1];print(*s(s(I(),I()),I()))

### FIXED CODE ###

I=lambda:list(map(int,input().split()));x,y,z,k=I();s=lambda a,b:sorted(i+j for i in a for j in b)[:-k-1:-1];print(*s(s(I(),I()),I()))
### BUGGY CODE ###

def resolve():
    n = int(input())
    P = list(map(int, input().split()))
    c = 0
    for i in range(n):
        if P[i] <= min(P[:i+1]):
            c += 1
    print(c)
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    P = list(map(int, input().split()))
    c = 0
    mn = P[0]
    for i in range(n):
        if mn >= P[i]:
            c += 1
            mn = P[i]
    print(c)
resolve()
### BUGGY CODE ###

n,m=map(int,input().split())
if m==0:
  print(0,0)
else:
  p=[list(map(str,input().split())) for i in range(m)]
  q=[]
  s=[0]*n
  t=0
  for i in range(m):
    if p[i][1]=='AC' and  not p[i][0] in q:
      q.append(p[i][0])
      
      t+=s[int(p[i][0])-1]
      
      
    elif p[i][1]=="WA":
      if not p[i][0] in q:
        s[int(p[i][0])-1]+=1
        
  
  
  
  
  print(len(q),t)
  

### FIXED CODE ###

n,m=map(int,input().split())
if m==0:
  print(0,0)
else:
  q=[0]*(n+1)
  s=[0]*(n+1)
  t=0
  for i in range(m):
    p,u=map(str,input().split())
    p=int(p)
    if q[p]==1:
      continue
    
    elif u=='AC':
      q[p]=1
      
      t+=s[p]
      
      
    elif u=="WA":
      if q[p]==0:
        s[p]+=1
        
  
  
  
  
  print(sum(q),t)
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
n,m=n1()
ab=n3(m)

ans={}
d=[0]*(n+1)
p=[1]
p2=[]
while len(ans)<n-1:
    for c in p:
        d[c]=1
        for a,b in ab:
            if a==c and d[b]==0:
                p2.append(b)
                d[b]=1
                ans[b]=a
            if b==c and d[a]==0:
                p2.append(a)
                d[a]=1
                ans[a]=b
    p=p2.copy()
    p2=[]

A=list(ans.items())
A.sort(key=lambda x:x[0])
print("Yes")
for line in A:
    print(line[1])

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right

n,m=n1()
ab=n3(m)

node=defaultdict(list)
for a,b in ab:
    node[a].append(b)
    node[b].append(a)
    
p=deque([1])
d=[0]*(n+1)
while len(p)>0:
    c=p.popleft()
    for i in node[c]:
        if d[i]==0:
            d[i]=c
            p.append(i)
            
print("Yes")
for i in range(2,n+1):
    print(d[i])
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n,k,q = map(int,input().split())
    a=[int(input()) for _ in range(q)]
    point=[k for i in range(n)]
    for i in range(q):
        for j in range(n):
            if(j!=(a[i]-1) and point[j]>0):
                point[j]-=1
    
    for i in range(n):
        if(point[i]>0):
            print("Yes")
        else:
            print("No")

main()

### FIXED CODE ###

n,k,q = map(int,input().split())
a=[int(input()) for _ in range(q)]
point=[k-q for i in range(n)]
for i in range(q):
    point[a[i]-1]+=1
 
for i in range(n):
    if(point[i]>0):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

def solve(x):
    if m % x == 0:
        return True
    else:
        return False
for i in range(m//n,-1,-1):
    if solve(i):
        print(i)
        exit()
    else:
        continue

### FIXED CODE ###

n,m = map(int,input().split())
 
def solve(x):
    if m % x == 0:
        return True
    else:
        return False
for i in range(m//n,-1,-1):
    if solve(i):
        print(i)
        exit()
    else:
        continue
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))

R = N
for i in range(0,N):
    t = A[i]
    for j in range(i+1,N):
        if not (t & A[j]):
            R += 1
            t += A[j]
        else:
            break
print(R)


### FIXED CODE ###

N = int(input())
A = tuple(map(int,input().split()))

result = 0
Right = 0
tmp = 0
for left in range(N):
    for right in range(Right,N):
        if not (tmp & A[right]):
            tmp += A[right]
            Right = right + 1
        else:
            break
    tmp -= A[left]
    result += Right - left
print(result)
### BUGGY CODE ###

from heapq import heappush, heappop
import itertools
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx,sy,0)]
data+=[tuple(map(int,input().split())) for i in range(n)]
data.append((gx,gy,0))

for i,j in itertools.product(range(n+2), range(n+2)):
    if i>=j:
        continue
    tmp=((data[i][0]-data[j][0])**2+(data[i][1]-data[j][1])**2)**0.5-data[i][2]-data[j][2]
    g[i].append((tmp,j))
    g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
dist[0]=0
visited=[False for i in range(n+2)]
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=max(x[0],0)+c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

class Node(object):
    def __init__(self, id):
        self.id = id
        self.value = 0
        self.parent_id = []
        self.children_id = []

    def set_parent(self, parent_id):
        self.parent_id.append(parent_id)

    def set_child(self, child_id):
        self.children_id.append(child_id)

    def add_number(self, n):
        self.value += n
        for child_id in self.children_id:
            nodes[child_id].add_number(n)

    def get_value(self):
        return self.value


N, Q = map(int, input().split())

nodes = []
for i in range(N + 1):
    nodes.append(Node(i))

for j in range(N - 1):
    parent, child = map(int, input().split())
    nodes[parent].set_child(child)
    nodes[child].set_parent(parent)

for _ in range(Q):
    parent, number = map(int, input().split())
    nodes[parent].add_number(number)

res = []
for k in range(1, N + 1):
    res.append(nodes[k].get_value())

print(*res, sep=' ')


### FIXED CODE ###

N, Q = map(int, input().split())

nodes = [0 for _ in range(N + 1)]

branches = []
for j in range(N - 1):
    parent, child = map(int, input().split())
    branches.append([parent, child])

for _ in range(Q):
    parent, number = map(int, input().split())
    nodes[parent] += number

branches.sort()

for branch in branches:
    parent = branch[0]
    child = branch[1]
    nodes[child] += nodes[parent]

print(*nodes[1:], sep=' ')
### BUGGY CODE ###

n,k = list(map(int,input().split()))
c = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if (i+j)%k != 0:
            continue
        for l in range(1,n+1):
            if (j+l)%k == 0 and (i+l)%k == 0:
                c += 1
print(c)

### FIXED CODE ###

n,k = list(map(int,input().split()))
if k & 1 == 1:
    print((n//k)**3)
else:
    print((n//k)**3+((n-(k>>1))//k+1)**3)
### BUGGY CODE ###

S = input()
NQ = int(input())

for i in range(NQ):
    query = input().split()
    if (int(query[0]) == 1):
        S = S[::-1]
    else:
        if (int(query[1]) == 1):
            S = query[2] + S
        else:
            S = S + query[2]

print(S)


### FIXED CODE ###

S = input()
NQ = int(input())

reverseFlag = False
prefix = ""
suffix = ""

for i in range(NQ):
    query = input().split()
    if (int(query[0]) == 1):
        reverseFlag = not reverseFlag
    else:
        if (reverseFlag):
            if (int(query[1]) == 1):
                suffix = suffix + query[2]
            else:
                prefix = query[2] + prefix
        else:
            if (int(query[1]) == 1):
                prefix = query[2] + prefix
            else:
                suffix = suffix + query[2]

if (reverseFlag):
    print(suffix[::-1] + S[::-1] + prefix[::-1])
else:
    print(prefix + S + suffix)
### BUGGY CODE ###

N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

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

sum_now = 0
DP = [[0] * (sum(aaa)+1) for i in range(N)]
DP2 = [[0] * (sum(aaa)+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	for j in range(sum_now + 1):
		DP[i][j] += DP[i-1][j] * 2
		DP[i][j] %= mod
		DP[i][j + a] += DP[i-1][j]

		DP2[i][j] += DP2[i-1][j]
		DP2[i][j] %= mod
		DP2[i][j + a] += DP2[i-1][j]

	sum_now += a

# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum(aaa) %2 == 0):
	num_too_long -= DP2[N-1][int(sum(aaa) /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )


### FIXED CODE ###

N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

aaa = [int(input()) for _ in range(N)]
sum_aaa = sum(aaa)

sum_now = 0
DP = [[0] * (sum_aaa+1) for i in range(N)]
DP2 = [[0] * (sum_aaa+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 1):

		if (j >= a):
			DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-a]
		else:
			DP[i][j] = DP[i-1][j]*2

		while (DP[i][j] > mod):
			DP[i][j] -= mod

	for j in range(min(sum_now + 1, int(sum_aaa /2)+1)):
		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

		while (DP2[i][j] > mod):
			DP2[i][j] -= mod

# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum_aaa %2 == 0):
	num_too_long -= DP2[N-1][int(sum_aaa /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )
### BUGGY CODE ###

import bisect

S=input()
dig=len(S)
N=int(S)


ans=0

b=0#繰り上がり
for i in range(dig):
    a=N%10+b
    if a<=4:
        ans+=a
        b=0
    elif a>=6:
        ans+=(10-a)
        b=1
    else:#a==5
        if (N%100 - N%10)//10 >=5:
            b=1
        else:
            b=0
        ans+=5
 
    N=N//10

        

if b==1:
    ans+=1

    
print(ans)
    
    

### FIXED CODE ###

import bisect

S=input()
dig=len(S)

ans=0

b=0#繰り上がり
for i in range(dig):
    a=int(S[dig-i-1])+b
    if a<=4:
        ans+=a
        b=0
    elif a>=6:
        ans+=(10-a)
        b=1
    else:#a==5
        if i==dig-1:
            ans+=5
            b=0
        else:
            if int(S[dig-i-2])>=5:
                b=1
            else:
                b=0
            ans+=5


        

if b==1:
    ans+=1

    
print(ans)