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

# a < b + c
# b < a + C
# c < a + b

# 4 3 2 1
# a b c 

# abs(a - b) < c < a + b
# a < b < c
# b - a < b < c
# c < a + b 

from math import ceil, floor
from bisect import bisect_left, bisect_right

def solution(N, data): # O(N^2 * logN)
    data.sort()
    c = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            # c += bisect_left(data, data[i] + data[j], j) - j - 1
            c += bisect_left(data[j+1:], data[i] + data[j])


    return c

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)



### FIXED CODE ###

# a < b + c
# b < a + C
# c < a + b

# 4 3 2 1
# a b c 

# abs(a - b) < c < a + b
# a < b < c
# b - a < b < c
# c < a + b 

from math import ceil, floor
from bisect import bisect_left, bisect_right

def solution(N, data): # O(N^2 * logN)
    data.sort()
    c = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            c += bisect_left(data, data[i] + data[j], j) - j - 1

    return c

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
k=0
for i in range(n):
    for j in range(i+1,n):
        if abs(a[i]+a[j])==abs(j-i):
            k+=1
print(k)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
k=0
b={}
for i in range(n):
    if a[i]+i in b:
        b[a[i]+i]+=1
    else:
        b[a[i]+i]=1
    if i-a[i] in b:
        k+=b[i-a[i]]
print(k)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
for i in A:
  AA = A.copy()
  AA.remove(i)
  print(max(AA))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)
MAX1, MAX2 = B[-1], B[-2]

for i in A:
  if i == MAX1:
    print(MAX2)
  else:
    print(MAX1)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

idx = [s[i:i+2] == "AC" for i in range(n-1)]

for i in range(q):
    print(sum(idx[lr[i][0]-1:lr[i][1]-1]))


### FIXED CODE ###

n,q = map(int, input().split())
s = input()
# lr = [list(map(int, input().split())) for i in range(q)]

idx = [0] * n

# idx = [idx[i-1]+int(s[i-1:i+1] == "AC") for i in range(1, n)]
for i in range(1,n):
    idx[i] = idx[i-1] + (s[i-1:i+1] == "AC")


for i in range(q):
    l,r = map(int, input().split())
    print(idx[r-1]-idx[l-1])
### BUGGY CODE ###

N,X,Y=map(int,input().split())

G=[[i+1] for i in range(N)]
G[N-1].pop()
for i in range(1,N):
    G[i].append(i-1)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

from collections import deque

q=deque([])
cnt=[0]*N

for n in range(N-1):
    seen=[0]*N
    q.append([n,0])
    seen[n]=1
    while q:
        x,c=q.popleft()
        if c>=N-1:continue
        for g in G[x]:
            if seen[g]==0:
                q.append([g,c+1])
                seen[g]=1
                if n<g:
                    cnt[c+1]+=1
for i in range(1,N):
    print(cnt[i])


### FIXED CODE ###

N,X,Y=map(int,input().split())

G=[[i+1] for i in range(N)]
G[N-1].pop()
for i in range(1,N):
    G[i].append(i-1)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

from collections import deque

q=deque([])
cnt=[0]*N

for n in range(N-1):
    seen=[0]*N
    q.append([n,0])
    seen[n]=1
    while q:
        x,c=q.popleft()
        if c>=N-1:continue
        for g in G[x]:
            if seen[g]==0:
                q.append([g,c+1])
                seen[g]=1
                if n<g:
                    cnt[c+1]+=1
for i in range(1,N):
    print(cnt[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
xy = [map(int, input().split()) for _ in range(Q)]
x, y = [list(i) for i in zip(*xy)]


def replace_list(num_list):
    num_list = [y[index] if j==i else j for j in num_list]
    return num_list




for index, i in enumerate(x):
    #first_sum = sum(A)
    #c = collections.Counter(A)
    #first_sum = c[i]*(y[index]-i)+first_sum
    while i in A :
        A.remove(i)  #全てのiを削除します。
        A.append(y[index])
    first_sum = sum(A)
    print(first_sum)
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
xy = [map(int, input().split()) for _ in range(Q)]
b, c = [list(i) for i in zip(*xy)]

sum_num = sum(A)
counter = collections.Counter(A)

for i in range(Q):
    sum_num -= counter[b[i]]*b[i] #counter[x]でxの個数をカウント
    sum_num += counter[b[i]]*c[i] #cで上書きされたので、c*counter[b]になる
    counter[c[i]] += counter[b[i]]
    counter[b[i]] = 0
    print(sum_num)
### BUGGY CODE ###

n,m = map(int,raw_input().split())
keys = [0]*m
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	keys[i] = (mask,a)

dp = []
M = 1<<n
for i in xrange(m+1):
	dp.append([10**9]*M)
	dp[i][0] = 0
	
for i in xrange(m):
	key = keys[i]
	for j in xrange(M):
		k = j|keys[i][0]
		dp[i+1][k] = min(dp[i+1][k], dp[i][j]+keys[i][1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
 
if dp[m][M-1] >= 10**9:
	print -1
else:
	print dp[m][M-1]

### FIXED CODE ###

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

M = 1<<n
dp = [10**9]*M
dp[0] = 0
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	for j in xrange(M):
		dp[j|mask] = min(dp[j|mask], dp[j]+a)
	#print dp
 
if dp[M-1] >= 10**9:
	print -1
else:
	print dp[M-1]
### BUGGY CODE ###

import collections
import sys
input=sys.stdin.readline

def calc():
  h,w,k=map(int,input().split())
  sy,sx,gy,gx=map(int,input().split())
  sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
  board=[input() for _ in range(h)]
  q=collections.deque()
  q.append((sx,sy))
  checked=[[0]*w for _ in range(h)]
  checked[sy][sx]=1
  cost=[[10**18]*w for _ in range(h)]
  cost[sy][sx]=0
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  while len(q)!=0:
    x,y=q.popleft()
    c=cost[y][x]
    for i in range(4):
      for j in range(1,k+1):
        if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
          break
        if board[y+j*dy[i]][x+j*dx[i]]=='@':
          break
        if cost[y+j*dy[i]][x+j*dx[i]]<=c:
          break
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
  if cost[gy][gx]==10**18:
    print(-1)
  else:
    print(cost[gy][gx])
calc()

### FIXED CODE ###

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

color = []
color.append(a.pop(0))
for ai in a:
    #color.sort(reverse=True)
    clen = len(color)
    for i, c in enumerate(color): 
        if ai > c:
            color[i] = ai
            break
        else:
            if i+1 == clen:
                color.append(ai)
                break
print(len(color))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
from collections import deque
import bisect

color = deque([a.pop(0)])
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.appendleft(ai)
print(len(color))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
maxketa = max([len(bin(a[i])) for i in range(n)])-2
mod = 10**9+7
ans = 0
for i in range(maxketa):
	ones = 0
	for j in range(n):
		if (a[j] >> i) & 1:
			ones += 1
	ans = (ans + (n-ones)*ones*(2**i)) % mod

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
maxketa = max([len(bin(a[i])) for i in range(n)])-2
mod = 10**9+7
ans = 0
for i in range(maxketa):
	ones = 0
	for j in range(n):
		if (a[j] >> i) & 1:
			ones += 1
	ans = (ans + (n-ones)*ones*(2**i)) % mod
 
print(ans)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        self.angle = None
dp = [[node() for j in range(m+1)] for i in range(n+1)]
for i in range(1,n + 1):
    dp[i][0].angle = Angle.UP
for j in range(1,m + 1):
    dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        same = dp[i][j].value + 1 if s[i] == t[j] else -1
        up = dp[i][j+1].value
        left = dp[i+1][j].value
        option = [same, up, left]
        max_index = option.index(max(option))
        dp[i + 1][j + 1].value = max(option)
        dp[i + 1][j + 1].angle = max_index
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].angle,end="")
#     print("")
i = n
j = m
ans=[]
while dp[i][j].angle != None:
    if dp[i][j].angle == Angle.DIAGONAL:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif dp[i][j].angle == Angle.UP:
        i -= 1
    else:
        j -= 1
print("".join(reversed(ans)))

        

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
ab_list = []
c_bit_list = []
INF = 1000000000
for _ in range(M):
    a,b = list(map(int,input().split()))
    ab_list.append([a,b])
    c=0
    c_in = list(map(int,input().split()))
    for k in range(b):
        c |= 1<<(c_in[k]-1)
    c_bit_list.append([c,a])

dp_all_number = pow(2,N)
c_bit_list_len = len(c_bit_list)
dp = [INF for _ in range(dp_all_number)]
dp[0] = 0

for i in range(dp_all_number):
    for j in range(c_bit_list_len):
        #print(i,j)
        dp[i | c_bit_list[j][0]] = min(dp[i | c_bit_list[j][0]],dp[i]+c_bit_list[j][1])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

N,M = map(int,input().split())
ab_list = []
c_bit_list = []
INF = 1000000000
for _ in range(M):
    a,b = list(map(int,input().split()))
    ab_list.append([a,b])
    c=0
    c_in = list(map(int,input().split()))
    for k in range(b):
        c |= 1<<(c_in[k]-1)
    c_bit_list.append([c,a])

dp_all_number = pow(2,N)
c_bit_list_len = len(c_bit_list)
dp = [INF for _ in range(dp_all_number)]
dp[0] = 0

for i in range(dp_all_number):
    for j in range(c_bit_list_len):
        #print(i,j)
        dp[i | c_bit_list[j][0]] = min(dp[i | c_bit_list[j][0]],dp[i]+c_bit_list[j][1])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [0] * q
for i in range(q):
    lr[i] = list(map(int, input().split()))

for i in lr:
    si = s[i[0]-1:i[1]]
    count = 0
    for j in range(len(si)-1):
        if si[j] == 'A' and si[j+1] == 'C':
            count += 1
    print(count)



### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [0] * q

def inp(l: list) -> list:
    return [int(l[0]) - 1, int(l[1]) - 1]

for i in range(q):
    lr[i] = tuple(inp(input().split()))

count = [0]*n
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        count[i] = count[i-1] + 1
    else:
        count[i] = count[i-1]

# print(count)

for l, r in lr:
    print(count[r] - count[l])
### BUGGY CODE ###

x = int(input())

def a(lst, target, with_replacement=False):
    def _a(idx, l, r, t, w):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u if w else (u + 1), l + [lst[u]], r, t, w)
        return r
    return _a(0, [], [], target, with_replacement)

goods = [100, 101, 102, 103, 104, 105]

res = a( goods, x, True)
print(1) if len(res)>0 else print(0)

### FIXED CODE ###

x = int(input())
cnt = int(x/100)

print(1) if x-cnt*105<=0 else print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
for i in range(1,n+1):
    try:
        print(a.count(i))
    except:
        print(0)

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
for i in range(1,n+1):
    if i in c:
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

S = list(input())
q = int(input())
procedure = [list(input().split()) for i in range(q)]

cnt = 0

for i in range(q):
    if procedure[i][0] == '1':
        cnt += 1
    if procedure[i][0] == '2':
        if (procedure[i][1] == '1' and cnt%2 == 0) or (procedure[i][1] == '2' and cnt%2 == 1):
            S.insert(0,procedure[i][2])
        else:
            S.append(procedure[i][2])

if cnt%2 == 1:
    S.reverse()
    
print(''.join(S))

### FIXED CODE ###

S = list(input())
q = int(input())
procedure = [list(input().split()) for i in range(q)]

cnt = 0
S2 = []

for i in range(q):
    if procedure[i][0] == '1':
        cnt += 1
    if procedure[i][0] == '2':
        if (procedure[i][1] == '1' and cnt%2 == 0) or (procedure[i][1] == '2' and cnt%2 == 1):
            S2.append(procedure[i][2])
        else:
            S.append(procedure[i][2])

S2.reverse()
S = S2 + S
if cnt%2 == 1:
    S.reverse()

print(''.join(S))
### BUGGY CODE ###

s = int(input())
k = int(input())
 
ans=0
 
n  = 5000000000000000
 
S = str(s) #文字列にする
saisho = 0
 
for i in range(len(S)):
  N = int(S[i])
  if k <= saisho+1:#最初からの文字数
    ans = N
    break
    
  else:
    saisho += N**n
    
print(ans)

### FIXED CODE ###

s = int(input())
k = int(input())
S = str(s) #文字列にする

ans=0

for i in range(k):
  N = int(S[i])
  
  if N == 1:
    ans = 1
  else:
    ans = N
    break  
print(ans)
### BUGGY CODE ###

#尺取り法と累積和
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [(i - 1) for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0] % k
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
for i in range(k):
    count[i] = 0
q = deque()
for i in acc_a:
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)

### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [(i - 1) for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0] % k
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
q = deque()
for i in acc_a:
    if i not in count:
        count[i] = 0
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)
### BUGGY CODE ###

h,w,m = list(map(int,input().split()))
t = [list(map(int,input().split())) for _ in range(m)]
from collections import Counter

x,y = zip(*t)
xcnt = Counter(x)
ycnt = Counter(y)

xcmax = max( xcnt.values() )
ycmax = max( ycnt.values() )
xlist = [k for k,v in xcnt.items() if v == xcmax]
ylist = [k for k,v in ycnt.items() if v == ycmax]
xylist = [ str(i) + '_' + str(j) for i in xlist for j in ylist ]
tlist = [ str(i[0]) + '_' + str(i[1])  for i in t ]
if len( set(xylist) - set(tlist) ) == 0:
  print( xcmax + ycmax -1 )
else:
  print( xcmax + ycmax )

### FIXED CODE ###

h,w,m = list(map(int,input().split()))
t = [list(map(int,input().split())) for _ in range(m)]
from collections import Counter
 
x,y = zip(*t)

xcnt = Counter(x)
ycnt = Counter(y)
 
xcmax = max( xcnt.values() )
ycmax = max( ycnt.values() )
xlist = [k for k,v in xcnt.items() if v == xcmax]
ylist = [k for k,v in ycnt.items() if v == ycmax]
if len(xlist) * len(ylist) > m:
  print( xcmax + ycmax )
else:
  xylist = { i*(10**6)+j for i in xlist for j in ylist }
  tlist = { i[0]*(10**6) + i[1] for i in t }
  if len( xylist - tlist ) == 0:
    print( xcmax + ycmax -1 )
  else:
    print( xcmax + ycmax )
### BUGGY CODE ###

import sys

x = int(input())

if x >= 2000:
    print(1)
    sys.exit()

for a in range (0,19):
    for b in range (0,19):
        for c in range (0,19):
            for d in range (0,19):
                for e in range (0,19):
                    for f in range (0,19):
                        total = 100*a + 101*b + 102*c + 103*d + 104*e + 105*f
                        if total == x:
                            print(1)
                            sys.exit()

print(0)

### FIXED CODE ###

x = int(input())

# 商品の合計がi個の場合の可能なxの範囲
# i=1   100-105
# i=2   200-210
# i=3   300-315
# i=4   400-420
# i=5   500-525
# i=6   600-630
# i=7   700-735
# i=8   800-840
# i=9   900-945
# ...
# i=19 1900-1995
# i=20以降は常に1

i = x // 100

if 100*i <= x <= 105*i:
  print(1)
else:
  print(0)
### BUGGY CODE ###

a = input()
b = input()
c = list(b)
d = 0
e = []
for i in range(len(c)+1):  #左からi個を白にする
    if i == 0: #全て黒に変える場合
        e.append(c.count("."))
        ans = e[0]
    else:
        if c[i-1] == ".":
            d = d + 1
        e.append(((i - d) + (c.count(".") - d)))
        if ans >= e[i]:
            ans = e[i]
print(ans)

### FIXED CODE ###

a = input()
b = input()
c = list(b)
d = 0
e = c.count(".")
f = 0
for i in range(len(c)+1): #左からi個を白にする　0<=i<=len(c)
    if i == 0:
        ans = e
    else:
        if c[i-1] == ".":
            d = d + 1 #dは左からi個のうちの白の個数を指す
        f = (i - d) + (e - d) #左側の(i-d)個の黒を白にし、右側(e-d)個の白を黒にする
        ans = min(ans, f)
print(ans)
### BUGGY CODE ###

import math

N=int(input())
A=[0]*N
for i in range(N):
  A[i] = int(input())

S = sum(A)
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][S]=1
for i in range(1,N+1):
  for j in range(math.ceil(S/2),S+1):
    if j+A[i-1] <= S:
      dp[i][j] = dp[i-1][j+A[i-1]]*2 + dp[i-1][j]
    else:
      dp[i][j] = dp[i-1][j]
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][S]=1
  for i in range(1,N+1):
    for j in range(math.ceil(S/2),S+1):
      if j+A[i-1] <= S:
        dp2[i][j] = dp2[i-1][j+A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)
### BUGGY CODE ###

N, W = map(int, input().split())
items = [[0, 0]]
for _ in range(N):
    items.append(list(map(int, input().split())))

dp = [[float("inf") for _ in range(10 ** 5 + 1)] for _ in range(N + 1)]

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

ans = 0
for i in range(1, N + 1):
    for j in range(N * (10 ** 3) + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
        if dp[i][j] <= W:
            ans = max(ans, j)

print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
items = [[0, 0]]
v_total = 0
for _ in range(N):
    w, v = map(int, input().split())
    items.append([w, v])
    v_total += v

dp = [[float("inf")] * (v_total + 1) for _ in range(N + 1)]

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

ans = 0
for i in range(1, N + 1):
    for j in range(v_total + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

        if i == N and dp[i][j] <= W:
            ans = max(ans, j)

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

N,M = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
B = [0]*M
for j in range(M):
	B[j] = list(map(int,input().split(" ")))

tmp = sorted(B,key=lambda x:x[1],reverse=True)
A.sort()

for i in tmp:
	for k in range(N):
		if i[1] > A[k] and i[0] > 0:
			A[k] = i[1]
			i[0] -= 1

print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
B = [0]*M
for j in range(M):
	B[j] = list(map(int,input().split(" ")))

tmp = sorted(B,key=lambda x:x[1],reverse=True)
A.sort()

r = 0
for i in tmp:
	for k in range(r,N,1):
		if i[1] > A[k] and i[0] > 0:
			A[k] = i[1]
			i[0] -= 1
			r = k+1
		elif A[k] > i[1] or i[0] == 0:
			break

print(sum(A))
### BUGGY CODE ###

import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = Counter(A)
    Q = int(input())
    for _ in range(Q):
        b,c = map(int, input().split())
        A[c] += A[b]
        A[b] = 0
        ans = 0
        for k,v in A.items():
            ans += k*v
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    suma = sum(A)
    A = Counter(A)
    Q = int(input())
    for _ in range(Q):
        b,c = map(int, input().split())
        suma -= A[b]*b
        suma += A[b]*c
        A[c] += A[b]
        A[b] = 0
        print(suma)

if __name__ == '__main__':
    main()