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

N, A, B = map(int, input().split())
round_count = 0

med = N / 2 + 0.5
maxAB = 10 ** 18

for i in range(maxAB):
    if abs(A - B) % 2 == 0:
        if A > B:
            A = A - 1
            B = B + 1

            if A < 1:
                A = 1
            elif B > N:
                B = N
        else:
            A = A + 1
            B = B - 1

            if A > N:
                A = N
            elif B < 1:
                B = 1
    else:
        Max = max([A, B])
        Min = min([A, B])
        if (Max + Min) / 2 > med:
            A = A + 1
            B = B + 1

            if A > N:
                A = N
            elif B > N:
                B = N
        else:
            A = A - 1
            B = B - 1

            if A < 1:
                A = 1
            elif B < 1:
                B = 1

    round_count = round_count + 1

    if A == B:
        break

print(round_count)

### FIXED CODE ###

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

med = N / 2 + 0.5
Sub = B - A

if (Sub) % 2 == 0:
    round_count = Sub // 2
else:
    round_count = min(A - 1, N - B) + 1 + (Sub - 1) // 2
            
print(round_count)
### BUGGY CODE ###

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

for i in range(q):
  sums = 0
  b,c = map(int, input().split())
  for j in range((len(a))):
    if a[j] == b:
      a[j] = c
    sums += a[j]
    
  print(sums)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
sums = sum(a)
d = {}

for i in a:
  if i in d:
    d[i] += 1
  else:
    d[i] = 1

for i in range(q):
    b,c = map(int, input().split())
    if b in d:
        sums += d[b]*(c-b)
        if c in d:
          d[c] += d[b]
        else:
          d[c] = d[b]
        d[b] = 0
    print(sums)
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_D
#?°´??????????????¢????¨????
import re

def cal_puddle(diagram_list):
    score = 0
    depth = 0
    for i, symbol in enumerate(diagram_list):
        if symbol == "\\":
            score += depth + 0.5
            depth += 1
        elif symbol == "/":
            depth = depth - 1
            score += depth + 0.5
        elif symbol == "_":
            score += depth
            
        if depth == 0:
            return (int(score),i)

    return (False, False)

def cal(diagram):
    
    puddle_areas = []
    diagram_list = []

    puddle_list = []
    i = 0
    score = []
    while i < len(diagram):
        if diagram[i] == "\\":
            res = cal_puddle(diagram[i:])
            if res[1]:
                i = i + res[1]
                score.append(res[0])
        i += 1

    return score

if __name__ == "__main__":
    a = input()
    result = cal(a)
    print(sum(result))
    print(str(len(result)) + "".join([" " + str(a) for a in result]))

### FIXED CODE ###

def cal_puddle(puddle):
    depth = 0
    score = 0
    for s in puddle:
        if s == "\\":
            score += depth + 0.5
            depth += 1
        elif s == "/":
            depth -= 1
            score += depth + 0.5
        elif s == "_":
            score += depth

        if depth == 0:
            return int(score)
    return int(score)

def get_puddles(diagram):
    hight = 0
    top_list = []
    in_puddle = True
    for index, s in enumerate(diagram + "\\"):
        if s == "/":
            in_puddle = True
            hight += 1
        if s == "\\":
            if in_puddle:
                in_puddle = False
                top_list.append([hight, index])
            hight -= 1

    puddles = []
    prev_hight = 0
    hight_list = [h for h, i in top_list]
    i = 0
    while i < len(top_list) - 1:
        cur_top = top_list[i]
        next_tops = list(filter(lambda top:cur_top[0] <= top[0], top_list[i + 1:]))
        #print(next_tops)
        if next_tops:
            next_top = next_tops[0]
            puddles.append((cur_top[1], next_top[1]))
            i = top_list.index(next_top)
        else:
            cur_top[0] -= 1
            cur_top[1] += diagram[cur_top[1] + 1:].index("\\") + 1
    #print(hight_list)
    #print(top_list)
    #print(puddles)
    return puddles

def main():
    diagram = input()
    result = []
    for s,e in get_puddles(diagram):
        result.append(cal_puddle(diagram[s:e]))
    print(sum(result))
    print(str(len(result)) + "".join([" " + str(i) for i in result]))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

H,W=map(int, raw_input().split())

A=[ [] for i in range(H) ]
for i in range(H):
	a=raw_input()
	for x in a:
		if x==".":
			A[i].append(0)
		else:
			A[i].append(float("inf"))


D=[ (-1,0),(1,0),(0,1),(0,-1)]


flag=False
cnt=1
for h in range(H):
	for w in range(W):
		u=A[h][w]	#point
		if u==float("inf"):
			for dx,dy in D:
				if 0<=h+dx<H and 0<=w+dy<W and A[h+dx][w+dy]==0:
					flag=True
					A[h+dx][w+dy]=cnt
else:
	if flag!=True:
		cnt-=1
		print cnt
		quit()



while True:
	flag=False
	cnt+=1
	for h in range(H):
		for w in range(W):
			u=A[h][w]	#point
			if u==cnt-1:
				for dx,dy in D:
					if 0<=h+dx<H and 0<=w+dy<W and A[h+dx][w+dy]==0:
						flag=True
						A[h+dx][w+dy]=cnt
	else:
		if flag!=True:
			cnt-=1
			print cnt
			quit()



### FIXED CODE ###

import sys
from collections import deque

H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

q=deque()

for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			q.append( (i,j) )
			K[i][j]=0


while q:
	h,w=q.popleft()
	for dx,dy in D:
		if 0<=h+dx<H and 0<=w+dy<W and K[h+dx][w+dy]>K[h][w]+1:
				K[h+dx][w+dy]=K[h][w]+1
				q.append( (h+dx,w+dy) )	

ans=0
for x in K:
	ans=max(ans, max(x) )
print ans
### BUGGY CODE ###

import numpy as np

N = int(input())
A = [0 for _ in range(N)]
B = [0 for _ in range(N)]

for i in range(N):
    a,b = map(int,input().split())
    A[i],B[i] = a,b

A = np.array(A)
B = np.array(B)

ans = 0
for i in range(N-1,-1,-1):
    a,b = A[i],B[i]

    if a%b != 0:
        ans += b - a%b
        A[:i+1] += b - a%b

print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
A = [0 for _ in range(N)]
B = [0 for _ in range(N)]

for i in range(N):
    a,b = map(int,input().split())
    A[i],B[i] = a,b

A = np.array(A)
B = np.array(B)

ans = 0
for i in range(N-1,-1,-1):
    a,b = A[i] + ans,B[i]

    if a%b != 0:
        ans += b - a%b

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

H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  for a in range(len(q)-1):
    p.append(cum[q[a+1]]-cum[q[a]])
  
  t_a = len(q)-2
  l = [0]*len(p)
  judge = False
  for w in range(W):
    for x,a in enumerate(p):
      y = a[w]
      if y>K:
        judge = True
        break
      else:
        l[x]+=y
        if l[x]>K:
          t_a+=1
          l = [0]*len(p)
          for z,b in enumerate(p):
            l[z] = b[w]
          break
    if judge:
      break
  if judge:
    continue
  else:
    ans = min(ans,t_a)
    
print(ans)

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

n=10**5
sievebd=n//2-1
sieve=[True]*sievebd
limit=(int((n-1)**.5)-1)//2
for i in range(limit):
    if sieve[i]:
        for j in range(2*i**2+6*i+3,sievebd,2*i+3):
            sieve[j]=False
for i in range((sievebd-1)//2-1,-1,-1):
    if not sieve[i]:sieve[2*i+1]=False
for i in range(2,sievebd,2):sieve[i]=False
q=int(input())
for i in range(q):
    l,r=map(lambda x:max(int(x),3),input().split())
    print(sum(sieve[(l-3)//2:(r-3)//2+1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n=10**5
sievebd=n//2
sieve=[True]*sievebd
limit=int(n**.5)//2
sieve[0]=0
for i in range(limit):
    if sieve[i]:
        for j in range(2*i*(i+1),sievebd,2*i+1):
            sieve[j]=False
for i in range((sievebd-1)//2,0,-1):
    if not sieve[i]:sieve[2*i]=False
for i in range(3,sievebd,2):sieve[i]=False
for i in range(1,sievebd):sieve[i]+=sieve[i-1]
q=int(input())
l=[list(map(int,input().split())) for _ in [0]*q]
for i in range(q):
    print(sieve[(l[i][1]-1)//2]-sieve[max(0,(l[i][0]-1)//2-1)])
### BUGGY CODE ###

s=input()
mod=10**9+7
cnt=0
for i in range(1,10**len(s)):
    temp=i
    if i%13==5:
        temp_str='0'*(len(s)-len(str(temp)))+str(temp)
        for x, y in zip(s, temp_str):
            if x != y and x!='?': break
        else:
            cnt += 1
print(cnt % mod)


### FIXED CODE ###

s=input()
len_s=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(len_s)]

if s[-1]!='?':
    dp[0][int(s[-1])%13]=1
else:
    for i in range(10):
        dp[0][i]=1

a=1
for i in range(1,len_s):
    a=10*a%13
    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*a)%13
        for j in range(13):
            dp[i][(amari+j)%13]+=dp[i-1][j]%mod

    else:
        for k in range(10):
            amari=(k*a)%13
            for l in range(13):
                dp[i][(amari+l)%13]+=dp[i-1][l]%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    max1 = max(p[i:(i+2)])
    max2 = min(p[i:(i+2)])
    ans += max2
    for j in range((n-i)-2):
        new = p[i+j+2]
        if max1 < new:
            max2 = max1
            max1 = new
        elif max2 < new:
            max2 = new
        ans += max2

print(ans)


### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

# 平方分割します。
max_n = 10**5
div_n = int(max_n**(1/2))+1
a = [[] for _ in range(div_n)]
a[0] = [0,0]
a[(n+1)//div_n].append(n+1)
a[(n+1)//div_n].append(n+1)
a_count = [0] * (div_n)
a_count[0] += 2
a_count[(n+1)//div_n] += 2

import bisect
ans = 0
for tmp in p_ind:
    val, i = tmp
    group = i//div_n
    j = bisect.bisect(a[group],i)
    #left
    if(j>1):
        left1 = a[group][j-1]
        left2 = a[group][j-2]
    elif(j==1):
        left1 = a[group][j-1]
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        left2 = a[lg][-1]
    else:
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        if(a_count[lg]>=2):
            left1 = a[lg][-1]
            left2 = a[lg][-2]
        else:
            left1 = a[lg][-1]
            while(True):
                lg -=1
                if(a_count[lg]>0):
                    break
            left2 = a[lg][-1]
    #right
    if(a_count[group]>=j+2):
        right1 = a[group][j]
        right2 = a[group][j+1]
    elif(a_count[group]>=j+1):
        right1 = a[group][j]
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        right2 = a[rg][0]
    else:
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        if(a_count[rg]>=2):
            right1 = a[rg][0]
            right2 = a[rg][1]
        else:
            right1 = a[rg][0]
            while(True):
                rg += 1
                if(a_count[rg]>0):
                    break
            right2 = a[rg][0]

    ans += ((right2 - right1)* (i - left1) + (right1 - i)* (left1 - left2)) * val
    a[group].insert(j,i)
    a_count[group] += 1

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

import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for i in range(n)]
w = sum(a)
mod =998244353

dp = [[0]*(w+1) for i in range(n)]

cnt = a[0]
dp[0][a[0]] = 1
dp[0][0] = 2
for i in range(1,n):
    cnt += a[i]
    for j in range(cnt+1):
        dp[i][j] = dp[i-1][j]*2
        if j >= a[i]:
            dp[i][j] += dp[i-1][j-a[i]]
        


#sより大きいのはブー
s = w//2+1
if w %2 == 0:
    d = [[0]*(s+1) for i in range(n)]
    d[0][0] = 1
    d[0][a[0]] = 1
    cnt = a[0]

    for i in range(1,n):
        cnt += a[i]
        for j in range(min(cnt+1,s+1)):
            d[i][j] = d[i-1][j]
            if j >= a[i]:
                d[i][j] += d[i-1][j-a[i]]
            d[i][j] = d[i][j]%mod
    mns = d[-1][w//2]
if w%2 == 0:
    s -= 1
cnt = 0
for i in range(s,w+1):
    cnt += dp[-1][i]
    cnt = cnt%mod

res = (pow(3,n,mod)-cnt*3)%mod

if w % 2 == 0:
    res = (res+mns*3)%mod
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for i in range(n)]
w = sum(a)
mod =998244353

dp = [[0]*(w+1) for i in range(n)]

cnt = a[0]
dp[0][a[0]] = 1
dp[0][0] = 2
for i in range(1,n):
    cnt += a[i]
    for j in range(cnt+1):
        dp[i][j] = dp[i-1][j]*2
        if j >= a[i]:
            dp[i][j] += dp[i-1][j-a[i]]
        
        dp[i][j] = dp[i][j]%mod

#sより大きいのはブー
s = w//2+1
if w %2 == 0:
    d = [[0]*(s+1) for i in range(n)]
    d[0][0] = 1
    d[0][a[0]] = 1
    cnt = a[0]

    for i in range(1,n):
        cnt += a[i]
        for j in range(min(cnt+1,s+1)):
            d[i][j] = d[i-1][j]
            if j >= a[i]:
                d[i][j] += d[i-1][j-a[i]]
            d[i][j] = d[i][j]%mod
    mns = d[-1][w//2]
if w%2 == 0:
    s -= 1
cnt = 0
for i in range(s,w+1):
    cnt += dp[-1][i]
    cnt = cnt%mod

res = (pow(3,n,mod)-cnt*3)%mod

if w % 2 == 0:
    res = (res+mns*3)%mod
print(res)
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      if n > 10000:
        if lst[i] >= lst[n-1] ** 0.5:
          continue
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          tf_lst[lst[i] * j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)


### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)
### BUGGY CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,750000,800000,825000,850000,875000,900000,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,10261678,10997400,11366472,11736253,12106789,12478098,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])


### FIXED CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 150000,200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,700000,720000,750000,800000,825000,850000,875000,900000,912500,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 1810893, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,9529244,9821778,10261678,10997400,11366472,11736253,12106789,12478098,12664043,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])
### BUGGY CODE ###

n = int(input())

e = [[] for _ in range(n)]
for i in range(n):
    a = map(int, input().split())
    for aa in a:
        aa -= 1
        e[i].append((i, aa))

inds = [0] * n
st = set(e[i][0] for i in range(n))
cnt = 0
while st:
    flg = False
    nst = set()
    for tpl in st.copy():
        x, y = tpl
        if x > y: continue
        if (y, x) in st:
            # print(st, x, y, inds)
            flg = True
            inds[x] += 1
            inds[y] += 1
            st.discard(tpl)
            st.discard((y, x))
            if inds[x] < n - 1:
                nst.add(e[x][inds[x]])
            if inds[y] < n - 1:
                nst.add(e[y][inds[y]])
            # print(nst)
    # print(st, nst, inds, flg)
    if not flg:
        print(-1)
        exit()

    cnt += 1
    st.update(nst)
print(cnt)


### FIXED CODE ###

def check(player):
    if not a[player]:
        return
    opponent = a[player][-1]
    if not a[opponent]:
        return
    if a[opponent][-1] == player:
        tpl = (player, opponent)
        q.add((min(tpl), max(tpl)))


n = int(input())

a = []
for _ in range(n):
    t = list(map(lambda x: int(x) - 1, input().split()))
    t.reverse()
    a.append(t)

q = set()
for i in range(n):
    check(i)

day = 0
while q:
    day += 1
    prev_q = set()
    q, prev_q = prev_q, q
    for player, opponent in prev_q:
        a[player].pop()
        a[opponent].pop()
    for player, opponent in prev_q:
        check(player)
        check(opponent)

if any(a[player] for player in range(n)):
    print(-1)
    exit()

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

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

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


### FIXED CODE ###

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

tmp = [0 for i in range(N+1)]

for i in ls:
  tmp[i] += 1

for i in range(1, N+1):
  print(tmp[i])
### BUGGY CODE ###

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

S = sum(A)

dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1

dp2 = [[0]*(S+1) for _ in range(N+1)]
dp2[0][0] = 1

for i in range(N):
    a = A[i]
    x = 0
    while x <= S:
        if x + a <= S:
            dp[i+1][x+a] += dp[i][x]
            dp2[i+1][x+a] += dp2[i][x]
        dp[i+1][x] += dp[i][x] * 2
        dp2[i+1][x] += dp2[i][x]
        x += 1



if S % 2 == 0:
    ans = 3 ** N - sum(dp[N][S//2:]) * 3
    ans += 3 * dp2[N][S//2]
else:
    ans = 3 ** N - sum(dp[N][S//2 + 1:]) * 3

print(ans % MOD)

### FIXED CODE ###

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

S = sum(A)

dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1

dp2 = [[0]*(S+1) for _ in range(N+1)]
dp2[0][0] = 1

for i in range(N):
    a = A[i]
    x = 0
    while x <= S:
        if x + a <= S:
            dp[i+1][x+a] += dp[i][x] % MOD
            dp2[i+1][x+a] += dp2[i][x] % MOD
        dp[i+1][x] += dp[i][x] * 2 % MOD
        dp2[i+1][x] += dp2[i][x] % MOD
        x += 1


if S % 2 == 0:
    ans = 3 ** N - sum(dp[N][S//2:]) * 3
    ans += 3 * dp2[N][S//2]
else:
    ans = 3 ** N - sum(dp[N][S//2 + 1:]) * 3

print(ans % MOD)
### BUGGY CODE ###

import sys, collections, math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
uq = []
chk = {}
for x in sys.stdin.readlines():
    x = x.rstrip()
    tmp = collections.Counter(sorted(x))
    h = ''
    for i in tmp:
        h += i + str(tmp[i])
    if h not in uq:
        uq.append(h)
    else:
        if h not in chk:
            chk.setdefault(h, 1)
        chk[h] += 1
ans = 0
for x in chk:
    ans += combinations_count(chk[x], 2)
print(ans)


### FIXED CODE ###

import sys, collections
n = int(input())
uq = ["".join(sorted(x.rstrip())) for x in sys.stdin.readlines()]
chk = collections.Counter(uq)
ans = 0
for x in chk:
    if chk[x] != 1:
        ans += chk[x]*(chk[x]-1)//2
print(ans)
### BUGGY CODE ###

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

ans = sum(A)
A = A+A

for k in range(1,N):
    L = [0]*N
    for l in range(N):
        T = A[N+l-k:N+l+1]
        L[l] = min(T)
    ans = min(ans,sum(L)+k*x)

print(ans)


### FIXED CODE ###

# AGC 004 B
N, x = map(int,input().split())
A = list(map(int,input().split()))

M = [[float("inf")]*N for k in range(N)]
for k in range(N):
    M[0][k] = A[k]

for k in range(N):
    for l in range(N):
        M[k][l] = min(M[k-1][l],A[k-l])

ans = sum(A)
for k in range(1,N):
    ans = min(ans,sum(M[k])+x*k)

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

import numpy as np
n,m = list(map(int,input().split()))
d = [[1<<n] for _ in range(m)]
for i in range(m):
  a,b = list(map(int,input().split()))
  d[i] = ((1<<a)-1) ^ ((1<<b)-1)

spr = [[False] for _ in range(m)]
s = 1<<0
for x in d:
  s |= x

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for i in range(n):
    if bit & 1<<i and s & 1<<i:
      for k in range(m):
        if (d[k] & 1<<i) > 0:
          spr[k] = False
      if sum(spr) == 0:
        ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))

print(ans)


### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

print(ans)