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

from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


dfs(0, N)
print(dp[0][-1])


### FIXED CODE ###

from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float(0)]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


# print(a_acc)
bfs()
# print(dp)
ans = int(dp[0][-1])
print(ans)
### BUGGY CODE ###

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-(m-1)*m*(2*m-1)//3
            ans=ans%INF
else:
    (n,m)=(m,n)
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-(m-1)*m*(2*m-1)//3
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)


### FIXED CODE ###

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)
### BUGGY CODE ###

N=int(input())
for h in range(1,3501):
  for n in range(1,3501):
    if 4/N-1/h-1/n!=0:
      w=1/(4/N-1/h-1/n)
      if abs(w-int(w))==0 and 0<w<10000:
        print(h,n,int(w),sep=" ")
        exit(0)

### FIXED CODE ###

N=int(input())
for h in range(int(N/4),3501):
  for n in range(h,3501):
    a=(4*h*n-N*(n+h))
    if a!=0:
      w=N*h*n/a
      if w==int(w) and 0<w<1000000000000:
        print(h,n,int(w),sep=" ")
        exit(0)
### BUGGY CODE ###

while 1:
    n=int(input())
    if n==0:break
    nlist=[]
    nans=-100001
    for i in range(n):
        nlist.append(int(input()))
        for j in range(i+1):
            nn=0
            for k in range(j,i+1):
                nn+=nlist[k]
            if nans<nn:nans=nn
    print(nans)


### FIXED CODE ###

while 1:
    n=int(input())
    if n==0:break
    nlist=[]
    nans=-100001
    for i in range(n):
        nlist.append(int(input()))
    nkeep=0
    for i in nlist:
        if nkeep<0:
            nkeep=i
        else:
            nkeep+=i
        if nans<nkeep:nans=nkeep
    if max(nlist)<0:nans=max(nlist)
    print(nans)
### BUGGY CODE ###

# encoding: "utf-8"

from collections import defaultdict

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def first_count_and_pop(xs):
    cnt = 0
    fst = xs[0]
    # cnt = xs.count(fst)
    for x in xs:
        if x != fst:
            break
        cnt += 1
    return (cnt, xs[cnt:])    
    

def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    xs.sort()
    ys = defaultdict(int)
    while xs:
        key = xs[0]
        cnt, xs = first_count_and_pop(xs)
        ys[key] += cnt
        ys[key-1] += cnt
        ys[key+1] += cnt

    print(max(ys.values()))

def main_():
    input()
    xs = Stdin.read_line(converter=int)
    xs.sort()
    counts = list()
    for i in range(100000):
        if not xs:
            counts.extend([0] * (100000 - len(counts)))
            break     
        elif i == xs[0]:
            cnt, xs = first_count_and_pop(xs)
            counts.append(cnt)
        else:
            counts.append(0)
    m = 0
    for i in range(0, 100000):
        if i == 0:
            temp = counts[i] + counts[i+1]
        elif i == 100000 - 1:
            temp = counts[i-1] + counts[i]
        else:
            temp = counts[i-1] + counts[i] + counts[i+1]
        if m < temp:
            m = temp
    print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###

import sys
n,m,l = map(int, input().split())

d=[[sys.maxsize]*(n+1) for _ in range(n+1)]
e=[[sys.maxsize]*(n+1) for _ in range(n+1)]
for i in range(n+1):
  d[0][i] = 0
  d[i][0] = 0
  d[i][i] = 0
  e[0][i] = 0
  e[i][0] = 0
  e[i][i] = 0

for _ in range(m):
  a,b,c = map(int, input().split())
  d[a][b]=c
  d[b][a]=c

for i in range(1,n+1):
  for j in range(1,n+1):#start
    for k in range(1,n+1):#end
      d[j][k]=min(d[j][k], d[j][i] + d[i][k])

for i in range(1,n+1):
  for j in range(1,n+1):
    if d[i][j] <= l:
      e[i][j] = 1

for i in range(1,n+1):
  for j in range(1,n+1):#start
    for k in range(1,n+1):#end
      e[j][k]=min(e[j][k], e[j][i] + e[i][k])

q=int(input())
for _ in range(q):
  s,t = map(int, input().split())
  if e[s][t] == sys.maxsize:
    print(-1)
  else:
    print(e[s][t]-1)


### FIXED CODE ###

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

d=[[sys.maxsize]*(n) for _ in range(n)]
e=[[sys.maxsize]*(n) for _ in range(n)]
for i in range(n):
  d[i][i] = 0
  e[i][i] = 0

for _ in range(m):
  a,b,c = map(int, input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c

d=floyd_warshall(csr_matrix(d))
for i in range(n):
  for j in range(n):
    if d[i][j] <= l:
      e[i][j] = 1

e=floyd_warshall(csr_matrix(e))

q=int(input())
for _ in range(q):
  s,t = map(int, input().split())
  if e[s-1][t-1] == sys.maxsize:
    print(-1)
  else:
    print(int(e[s-1][t-1]-1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                if dists[ny][nx] <= dists[y][x] + 10: break # gori~~
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()
### BUGGY CODE ###

import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline

import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

import bisect
def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    for a in A:
        if a > 0:
            c = x//a
            cnt += bisect.bisect_right(A, c)
        elif a < 0:
            c = (-x-1)//(-a)
            cnt += n - bisect.bisect_right(A, c)
        else:
            if x >= 0:
                cnt += n
    for a in A:
        if a*a <= x:
            cnt -= 1
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    m = (l+r)//2
    if ok(m):
        r = m
    else:
        l = m
print(r)


### FIXED CODE ###

import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline

import numpy as np

n, k = map(int, input().split())
A = np.array(input().split(), np.int64)
A = np.sort(A)

P = A[A>0]
Z = A[A==0]
N = A[A<0]

#t = n*(n-1)//2

def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    #cnt += np.searchsorted(A, np.ceil(x/P), side='right').sum()
    cnt += np.searchsorted(A, x//P, side='right').sum()
    #cnt += n-np.searchsorted(A, np.floor(x/N), side='left').sum()
    cnt += (n-np.searchsorted(A, (-x-1)//(-N), side='right')).sum()
    if x >= 0:
        cnt += len(Z)*n
    cnt -= np.count_nonzero(A*A <= x)
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)
### BUGGY CODE ###

import copy

n = int(input())
a_list = []
out_list = []

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

is_max = False
#print(a_list)    
for i in range(n):
    if not is_max:
        a_copy = copy.copy(a_list)
        a_copy.pop(i)
        #print(a_copy)
        a_max = max(a_copy)
        #print(a_max)
        out_list.append(a_max)
        if a_list[i] == a_max:
            is_max = True
    else:
        out_list.append(a_max)
        
print("\n".join(map(str, out_list)))

### FIXED CODE ###


n = int(input())
a = []

for i in range(n):
    a.append(int(input()))
    
a_copy = list(a)
a.sort(reverse=True)

max_1 = a[0]
max_count = a.count(max_1)

for i in a:
    if i < max_1:
        max_2 = i
        break
        
for a in a_copy:
    if a == max_1 and max_count == 1:
        print(max_2)
    else:
        print(max_1)
### BUGGY CODE ###

import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
lst_a.sort(reverse=True)
temp = 0
ans = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
for i in range(m):
    if lst_a[0] >= lst_a[1]:
        lst_a[0] //= 2
    else:
        lst_a[1] //= 2
        lst_a.sort(reverse=True)
print(sum(lst_a))


### FIXED CODE ###

import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
temp = 0
cnt = 0
fin = 0
loop = 0
debug = 0
temp2 = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
while debug < 10:
    loop = 0
    #temp2 = temp
    temp = 0
    lst_a.sort(reverse=True)
    while loop < n-1:
        lst_a[loop] //= 2
        cnt += 1
        temp = max(temp,lst_a[loop])
        if cnt == m:
            #print(lst_a)
            print(sum(lst_a))
            sys.exit()
        if temp > max(lst_a[loop],lst_a[loop + 1]):
            break
        if lst_a[loop + 1] > lst_a[loop]:
            loop += 1
        
        
        
"""        if lst_a[loop] >= max(lst_a[loop + 1],temp):
            lst_a[loop] //= 2
            temp = max(lst_a[loop],lst_a[loop+1])
            cnt += 1
            if cnt == m:
                print(sum(lst_a))
                sys.exit()
            if temp > lst_a[loop + 1]:
                break
            
            
        loop += 1
    
    #debug += 1
print(lst_a[99999])
# print(temp)
# print(cnt)
# print(lst_a)
# print(sum(lst_a))
"""
### BUGGY CODE ###

n, m = (int(x) for x in input().split())

B = []
A = list(int(x) for x in input().split())

for i in range(m):
    j, k = (int(x) for x in input().split())
    C = [j, k]
    B.append(C)

count = 0

for i in range(1, n + 1):
    D = []
    for l in B:
        if i in l:
            for a in l:
                D.append(a)
        else:
            pass
    b = set(D)
    apple = list(b)
    if len(apple) == 0:
        count += 1
    else:
        apple.remove(i)
        E = []
        for cat in apple:
            dog = A[cat - 1]
            E.append(dog)
        if A[i - 1] > max(E):
            count += 1
        else:
            pass
print(count)

### FIXED CODE ###

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


ans = [1] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if hs[a] < hs[b]:
        ans[a] = 0
    elif hs[a] == hs[b]:
        ans[a] = 0
        ans[b] = 0
    else:
        ans[b] = 0

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

import sys
from collections import deque


dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len, q_list):
    cnt = 0
    while len(q_list)>0:
        new_q_list = []
        for q in q_list:
            h, w = q[0], q[1]
            for dx, dy in zip(dx_list, dy_list):
                x = w + dx
                y = h + dy
                if 0 <= x < w_len and 0 <= y < h_len and m_list[y][x] == 0:
                    m_list[y][x] = 1
                    new_q_list.append([y, x])
        if len(new_q_list) == 0:
            break
        else:
            cnt += 1
            q_list = new_q_list
    return cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    m_list = []
    for _ in range(h_len):
        s = input()[:-1]
        m_list.append([1 if i == '#' else 0 for i in s])
    q_list = []
    for h, w_list in enumerate(m_list):
        for w, check in enumerate(w_list):
    	    if check == 1:
    		    q_list.append([h, w])
    ans = bfs(h_len, w_len, q_list)
    print(ans)
	

### FIXED CODE ###

def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)
### BUGGY CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

p = []
i = 0
while i < len(s) - 1:
    if s[i:i+2] == 'AC':
        p.append(i)
        i += 2
    else:
        i += 1

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)
    l, r = l - 1, r - 1

    if c == 0:
        print(0)
        continue

    # print(m)
    # print(l, r)
    # print(m[1:][r - 1], m[l])
    print(m[1:][r - 1] - m[l])

    # print()




### FIXED CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)

    if c == 0:
        print(0)
        continue
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
count_list = []

for s_point in range(N):
  point = s_point
  count = 0
  i = 0
  while i < N:
    point = T_list[point]
    if point == s_point:
      count = i+1
      break
    i += 1
  count_list.append(count)

point = 0
while count_list[point] == 0:
  point = T_list[point]
  count += 1

L = (K-count) % count_list[point]
new_point = 0
i = 0

while i < L:
  point = T_list[point]
  i += 1
print(point+1)

### FIXED CODE ###

N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
point = 0
syuuki = 0

if K < N:
  i = 0
  while i < K:
    point = T_list[point]
    i += 1  

else:
  i = 0
  while i < N:
    point = T_list[point]
    if point == 0:
      syuuki = i+1
      break
    i += 1
  second_point = point
  
  if syuuki != 0:
    L = K % syuuki

  else:
    j = 0
    while j < N:
      point = T_list[point]
      if point == second_point:
        syuuki = j+1
        break
      j += 1
    L = (K-i) % syuuki

  k = 0
  while k < L:
    point = T_list[point]
    k += 1
  
print(point+1)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
pari = [0] * 40
for i in range(40):
    for j in a:
        pari[i] += (j&(1<<i))>>i

ans = a[:]

for i in range(40):
    if pari[i]%2:
        for j in range(n):
            if a[j]&(1<<i):
                ans[j] -= 1<<i
            else:
                ans[j] += 1<<i

print(' '.join([str(i) for i in ans]))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
pari = [0] * 30
for i in range(30):
    for j in a:
        pari[i] += (j&(1<<i))>>i

ans = a[:]

for i in range(30):
    if pari[i]%2:
        for j in range(n):
            if a[j]&(1<<i):
                ans[j] -= 1<<i
            else:
                ans[j] += 1<<i

print(' '.join([str(i) for i in ans]))
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
ans = 0
now = 1
while(now != 2):
  ans += 1
  now = a[now-1]
  if(now == 1):
    ans = -1
    break
print(ans)


### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
frag = [True for _ in range(n)]
frag[0] = False
ans = 0
now = 1
while(now != 2):
  ans += 1
  now = a[now-1]
  if(frag[now-1]):
    frag[now-1] = False
  else:
    ans = -1
    break
print(ans)
### BUGGY CODE ###

def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    tmp = 1
    for i in range(k):
        tmp *= A[i]

    for j in range(k + 1, n + 1):
        x = tmp * 1
        tmp //= A[j - k - 1]
        tmp *= A[j - 1]
        if tmp > x:
            print("Yes")
        else:
            print("No")


solve()


### FIXED CODE ###

def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    for j in range(k + 1, n + 1):
        if A[j - k - 1] < A[j - 1]:
            print("Yes")
        else:
            print("No")


solve()
### BUGGY CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    dp1 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp2[0][0] = 1
    for i in range(N):
        for j in dp1[i]:
            dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j] * 2) % MOD
            dp1[i+1][j+A[i]] = (dp1[i+1][j+A[i]] + dp1[i][j]) % MOD
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % MOD
            dp2[i+1][j+A[i]] = (dp2[i+1][j+A[i]] + dp2[i][j]) % MOD

    ans = (3**N) % MOD
    for t in dp1[N]:
        if t >= -(-total//2):
            ans = (ans - dp1[N][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


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

n=int(input())

high=3500
low=1

for i in range(1,3501):
    for j in range(i,3501):
        while high-low>1:
            k=(high+low)//2
            x=4*(i*j*k)/(i*j+j*k+k*i)
            if n==x:
                print(i,j,int(k))
                exit()
                
            elif n>x:
                low=x                
            else:
                high=x
                    
                    
                    

    



### FIXED CODE ###

N=int(input())

for i in range(1,3501):
    for j in range(i,3501):
        if 4*i*j-N*i-N*j<=0:
            continue
        k=(N*i*j)/(4*i*j-N*i-N*j)
        if k>0 and k-(N*i*j)//(4*i*j-N*i-N*j)==0:
            print(i,j,int(k))
            exit()
### BUGGY CODE ###

h = int(input())
new_h = h
pow_num = 0
ans = 0
attack = 1
preattack = 1


while(1):
  new_h = new_h//2
  pow_num += 1
  if new_h == 1:
    break
for i in range(pow_num):
  preattack = preattack*2
  attack += preattack
print(attack)

### FIXED CODE ###

h = int(input())
new_h = h
pow_num = 0
ans = 0
attack = 1
preattack = 1

if h == 1:
  print("1")
  exit()
while(1):
  new_h = new_h//2
  pow_num += 1
  if new_h == 1:
    break
for i in range(pow_num):
  preattack = preattack*2
  attack += preattack
print(attack)