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

#!/usr/bin/env python
# coding: utf-8

# In[1]:


X, Y, Z, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]


# In[14]:


AB = []
for x in range(X):
    for y in range(Y):
        AB.append(A[x] + B[y])
AB.sort(reverse=True)
if K < X * Y:
    AB = AB[:K]
W = len(AB)
AB


# In[16]:


ABC = []
for w in range(W):
    for z in range(Z):
        ABC.append(AB[w] + C[z])
ABC.sort(reverse=True)
if K < W * Z:
    ABC = ABC[:K]
ABC


# In[17]:


print('\n'.join(map(str, ABC)))


# In[ ]:





# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


X, Y, Z, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]


# In[14]:


AB = []
for x in range(X):
    for y in range(Y):
        AB.append(A[x] + B[y])
AB.sort(reverse=True)
if K < X * Y:
    AB = AB[:K]
W = len(AB)
AB


# In[16]:


ABC = []
for w in range(W):
    for z in range(Z):
        ABC.append(AB[w] + C[z])
ABC.sort(reverse=True)
if K < W * Z:
    ABC = ABC[:K]
ABC


# In[17]:


print('\n'.join(map(str, ABC)))


# In[ ]:





# In[ ]:
### BUGGY CODE ###

H,W,K = map(int, input().split())
S = [list(map(int,(list(map(str,input().split()))[0]))) for i in range(H)]
#print(S)
import numpy as np
from itertools import product
"""
H,W,K = 3,5,2
S = [[1,1,1,0,0],
     [1,0,0,0,1],
     [0,0,1,1,1]]
"""

S = np.array(S).T

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):#分けるか分けないか
        ans = sum(X)#横に切った回数
        #print(ans)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])#切った回数箱を増やす
            M[-1].append(i+1)#後ろの箱に切る場所を入れていく
        #print(M)
        D = [0]*len(M)
        #print(D)
        for s in S:
            for k, m in enumerate(M):
                D[k] += np.sum(s[i] for i in m)
                #print("D",D)
            if any(d > K  for d in D):
                ans += 1
                #print("ans",ans)
                for k, m in enumerate(M):
                    D[k] = np.sum(s[i] for i in m)
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

a,b = map(int,input().split())
base = 1
for i in range(a,b+1):
    base = base * i
if base > 0:
    print('Positive')
elif base < 0:
    print('Negative')
else:
    print('Zero')

### FIXED CODE ###

import sys
a,b = map(int,input().split())
if a > 0:
    print('Positive')
    sys.exit()
if b >= 0:
    print('Zero')
    sys.exit()
if (b-a+1)%2 == 1:
    print('Negative')
else:
    print('Positive')
### BUGGY CODE ###

n = int(input())
S = list(str(input()))
ans = 0
for i in range(1000):
    q = 0
    p = list(str(i).zfill(3))
    s = p[q]
    for j in range(len(S)):
        if s == S[j]:
            q+=1
            if q == 3:
                break
            else:
                s = p[q]
        else:
            continue
    if q == 3:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
S = list(str(input()))
ans = 0
for i in range(1000):
    q = 0
    p = list(str(i).zfill(3))
    s = p[q]
    for j in range(len(S)):
        if s == S[j]:
            q+=1
            if q == 3:
                break
            else:
                s = p[q]
        else:
            continue
    if q == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

A,B,K = map(int,input().split())
l = []
for i in range(B-A+1):
  l.append(A+i)
del l[K:-K]
for e in l:
  print(e)

### FIXED CODE ###

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

s = input()
mods = []
crt = int(s[-1])
if len(s) <= 4:
    print(0)
    exit()
# for i in range(len(s)):
#     crt = crt*10+int(s[i])
#     crt %= 2019
#     mods.append(crt)
# print(mods)
for i in range(len(s)-2,-1,-1):
    crt = crt+int(s[i])*10**(len(s)-i-1)
    crt %= 2019
    mods.append(crt)
ans = 0
ans += mods.count(0)
modst = set(mods)
ans += len(mods) - len(modst)
print(ans)



### FIXED CODE ###

import collections
s = input()
mods = [0]
crt = 0
ans = 0
if len(s) <= 4:
    print(0)
    exit()
# for i in range(len(s)):
#     crt = crt*10+int(s[i])
#     crt %= 2019
#     mods.append(crt)
# print(mods)
for i in range(len(s)-1,-1,-1):
    crt = crt+int(s[i])*pow(10, (len(s)-i-1), 2019)
    crt %= 2019
    mods.append(crt)
#print(mods)
mods_count = collections.Counter(mods)
mods_count = list(mods_count.values())
for i in range(len(mods_count)):
    tar = mods_count[i]
    ans += tar*(tar-1)//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

A.sort(reverse=True)
#print(A)

ans = 0
list = []
for i in range(N):
  if ( i==0 ) :
    list.append(A[0])
  else:
    max_index = list.index(max(list))
    ans += list[max_index]
    list[max_index] = A[i]
    list.insert(max_index, A[i])
  #print(list,ans)

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

A.sort(reverse=True)
#print(A)

"""
ans = 0
list = []
for i in range(N):
  if ( i==0 ) :
    list.append(A[0])
  else:
    max_index = list.index(max(list))
    ans += list[max_index]
    list[max_index] = A[i]
    list.insert(max_index, A[i])
  #print(list,ans)
"""

ans = 0
for i in range(N):
  if ( i==0 ) :
    ans += 0
  else:
    ans += A[i//2]

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

n = int(input())

m=0
for i in range(n):
    m += i
print(m)


### FIXED CODE ###

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

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

for i in range(N):
  x = sorted(X[:i]+X[i+1:])
  print(x[len(x)//2])

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
sort_X = sorted(X)
l, r = sort_X[N//2-1], sort_X[N//2]
for x in X:
  if(x <= l):
    print(r)
  else:
    print(l)
### BUGGY CODE ###

N = int(input())
mod = 10**9 + 7
fac = [1 for _ in range(N+1)]
for i in range(N):
    fac[i+1] = (i+1)*fac[i]%mod

a = sorted([int(input()) for _ in range(N)])
b = sorted([int(input()) for _ in range(N)])
ab = list(zip(a,b))
X = [-2, -1]
ctr = 1
H = []
for i, j in ab:
    if i > j:
        i, j = j, i 
    if i < X[1]:
        X = [i,X[1]]
        ctr += 1
    else:
        H.append(ctr)
        ctr = 1
        X = i, j
ans = fac[ctr]
for i in H:
    ans = ans*fac[i]%mod
print(ans%mod)


### FIXED CODE ###

def nexts(X,Xs,Y,Ys):
    Z = (X+Y)//2
    print('{}\n'.format(Z))
    Zs = input()
    if Zs == 'Vacant':
        sys.exit()
    if (Xs == Zs and (Z-X)%2 == 1)\
    or (Xs != Zs and (Z-X)%2 == 0):
        Y, Ys = Z, Zs
    else:
        X, Xs = Z, Zs
    return X,Xs,Y,Ys

import sys

N = int(input())
print('0\n')
xs = input()
if xs == 'Vacant':
    sys.exit()
print('{}\n'.format(N-1))
ys = input()
if ys == 'Vacant':
    sys.exit()
x, y = 0, N-1
while True:
    x,xs,y,ys = nexts(x,xs,y,ys)
### BUGGY CODE ###

N=int(input())
H=[int(x) for x in input().split()]
A=''
for i in range(N-1):
  if H[i] >= H[i+1]:
    A += 'o'
  else:
    A +='x'
for j in range(1,N):
  if 'o'*(N-j) in A:
    print(N-j)
    exit()
print('0')

### FIXED CODE ###

N=int(input())
H=[int(x) for x in input().split()]
answer = 0
count = 0
for i in range(N-1):
  if H[i]>=H[i+1]:
    count +=1
    answer = max(answer,count)
  else:
    count=0
print(answer)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc152/tasks/abc152_e
# 見た瞬間にわかってしまった天才だ

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from fractions import gcd


def ret_inv(a, p):
    return pow(a, p - 2, p)


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a * b // g


N = read_a_int()
A = read_ints()
flat = 1
for a in A:
    flat = lcm(flat, a)

ans = 0
for a in A:
    ans += flat // a
    if ans >= MOD:
        ans %= MOD
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc152/tasks/abc152_e
# 見た瞬間にわかってしまった天才だ

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))

    if temp != 1:
        arr.append((temp, 1))

    if arr == []:
        arr.append((n, 1))

    return arr


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from fractions import gcd


def ret_inv(a, p):
    return pow(a, p - 2, p)


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a * b // g


N = read_a_int()
A = read_ints()

flat = defaultdict(lambda: 0)  # 素数がkey
for a in A:  # modで演算できるようにするか掛け算を実際には行わずに保持しておく必要がある。
    tmp = factorization(a)
    for k, v in tmp:
        flat[k] = max(flat[k], v)

flat_mod = 1
for k, v in flat.items():
    flat_mod *= pow(k, v, MOD)
    if flat_mod >= MOD:
        flat_mod %= MOD

ans = 0
for a in A:
    ans += flat_mod * ret_inv(a, MOD)
    if ans >= MOD:
        ans %= MOD
print(ans)
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
su = 0
bb = 0
for i in range(a):
	if b[i] < 0:
		co += 1
	elif b[i] > 0:
		coco += 1
	else:
		cococo += 1
	su += abs(b[i])

if co > coco:	
	while su != 0:
		bb = 0
		for i in range(a):
			b[i] += 1
			bb += abs(b[i])
		if bb > su:
			print(su)
			break
		su = bb
		bb = 0


elif coco >= co:
	while su != 0:
		for i in range(a):
			b[i] -= 1
			bb += abs(b[i])
		if bb > su:
			print(su)
			break
		su = bb
		bb = 0

if su == 0:
	print(0) 

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
su = 0
c = b[(a - 1) // 2]

for i in range(a):
	su += abs(b[i] - c)

print(su)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			U, R, D, L = 0, 0, 0, 0
			while i - U >= 0 and S[i - U][j] == ".":
				U += 1
			while i + D <= H - 1 and S[i + D][j] == ".":
				D += 1
			while j + R <= W - 1 and S[i][j + R] == ".":
				R += 1
			while j - L >= 0 and S[i][j - L] == ".":
				L += 1
			ans = max(ans, L + R + D + U - 3)
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			if j == 0:
				L[i][j] = 1
			else:
				L[i][j] = L[i][j - 1] + 1

# print(L)

for i in range(H):
	for j in range(W - 1, -1, -1):
		if S[i][j] == ".":
			if j == W - 1:
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

# print(R)

for j in range(W):
	for i in range(H - 1, -1, -1):
		if S[i][j] == ".":
			if i == H - 1:
				D[i][j] = 1
			else:
				D[i][j] = D[i + 1][j] + 1

# print(D)

for j in range(W):
	for i in range(H):
		if S[i][j] == ".":
			if i == 0:
				U[i][j] = 1
			else:
				U[i][j] = U[i - 1][j] + 1

# print(U)


ans = 0
X = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
	ans = max(ans, max(X[i]))

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

n = map(int, input())

ans = 1
for i in input().split():
    ans *= int(i)

print(ans if ans <= 10**18 else -1)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)


main()
### BUGGY CODE ###

#C
M = int(input())
A = list(map(int, input().split())) 

for i in range(1,M+1):
    print(A.count(i))

### FIXED CODE ###

#C
M = int(input())
A = list(map(int, input().split())) 
ans = [0] * M

for i in range(M-1):
    ans[int(A[i])-1]+=1
    
for a in ans:
    print(a)
### BUGGY CODE ###


n = int(input())

ans = 0

while n != 0:
    ans += n % 10
    n //= 10

if ans % 9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###


n = int(input())

ans = 0

l = [int(x) for x in list(str(n))]
ans = sum(l)

if ans % 9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7

count = 0
for i in range(len(s)):
    dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
    else:
        dp2['A'] = dp1['A']

    if s[i] == '?':
        dp2['AB'] = dp1['AB']*3 + dp1['A']
    elif s[i] == 'B':
        dp2['AB'] = dp1['AB'] + dp1['A']
    else:
        dp2['AB'] = dp1['AB']

    if s[i] == '?':
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    elif s[i] == 'C':
        dp2['ABC'] = dp1['ABC'] + dp1['AB']
    else:
        dp2['ABC'] = dp1['ABC']

    if s[i] == '?':
        count += 1

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2
    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c
    #print(i, dp1)

print(dp1['ABC'])


### FIXED CODE ###

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c
#print(tmp)

count = 0
for i in range(n):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])
### BUGGY CODE ###

from itertools import accumulate
n, k = map(int, input().split())
As = list(map(int, input().split()))

acc = [0]+list(accumulate(As))
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 計算
now = 0
for d in range(40,-1,-1):
    cnt = 0
    for s in sums:
        # 上から見て、bitが立っている数がk個以上かどうか
        # 最上位がkこ未満だったら、そのbitはもう使わない
        # 1000 -> 1100 -> 1100 -> 1101 みたいな絞り込み
        if s & (now|(1<<d)) == now|(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now |= 1<<d
print(now)

### FIXED CODE ###

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

from itertools import accumulate
acc = [0]+list(accumulate(As))
dp = [0] * 50
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 最大の桁数
for d in range(50):
    if max(sums) & (1<<d):
        mx = max(mx, d)
        dp[d] += 1
mx = 0
for i in range(50):
    if dp[i] >= k:
        mx = max(mx,i)

# 計算
ans = 0
now = 0
for d in range(50,-1,-1):
    cnt = 0
    for s in sums:
        if s & (now+(1<<d)) == now+(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now += 1<<d
print(now)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
N,M=map(int,input().split())
list1=list(map(int,input().split()))
for _ in range(M):
  B,C=map(int,input().split())
  list1+=[C]*B
list1=heapq.nlargest(N,list1)
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

N = int(input())
S = input()
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    elif S[i] == 'B':
        B.append(i)
ans = len(R)*len(G)*len(B)
for i in R:
    for j in G:
        if min(i,j)-abs(i-j) in B:
            ans -= 1
        if max(i,j)+abs(i-j) in B:
            ans -= 1
        if (i-j) % 2 == 0:
            if min(i,j)+abs(i-j)//2 in B:
                ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    elif S[i] == 'B':
        B.append(i)
ans = len(R)*len(G)*len(B)
for i in range(1,(N+1)//2):
    for j in range(i,N-i):
        if S[j] != S[j-i] and S[j] != S[j+i] and S[j-i] != S[j+i]:
            ans -= 1
print(ans)
### BUGGY CODE ###



def main():

    N,P = map(int, input().split())
    S = input()


    d = {}


    ans = 0
    for l in range(N):
        for r in range(l,N):
            if l == r:
                if int(S[l]) in d:
                    if d[int(S[l])] == 0:
                        ans += 1 
                else:
                    d[int(S[l])] = int(S[l]) % P
                    if d[int(S[l])] == 0:
                        ans += 1 
            else:
                if int(S[l:r+1]) in d:
                    if d[int(S[l:r+1])] == 0:
                        ans += 1 
                else:
                    d[int(S[l:r+1])] = int(S[l:r+1]) % P
                    if d[int(S[l:r+1])] == 0:
                        ans += 1 

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###




N,P = map(int, input().split())
S = input()

ans = 0
mod_P = [0] * P
mod_P[0] += 1
# P が 10と互いに素でないなら、U_i - U_jのうちのU_jがPで割り切れるだけでよい
if P in [2,5]:
    
    for i in range(N):
            """
            今見ているiかそれより左側にある物をU_iとして選択する場合に割り切れるようになるので、
            いまのiを含む左にあるものの個数を足す
            """
            if int(S[i]) % P == 0:
                ans += i+1
    
    print(ans)

else:
    """
    右端から見て、
    ([右端からi番目までの数字] - [右端からj番目までの数字]) % Pが0になるならOK
    [右端からi番目までの数字] % P = X となるなら、[右端からj番目までの数字] % P = X であれば割り切れる
    なので、i番目までを見ているときに、そこより右側で、余りがi番目までをPで割った時と同じになる個数が分かればよい。

    毎回律義にi番目までを数値化して、mod P をとってるとTLEになるので、
    右からi番目の数字 10 ** i + それまで
    の形で積み重ねていく。
    また、余りの問題なので、余りの世界で現在値を保存しておく(今回みたいな大きな値について毎回modをとるとめちゃくちゃ遅い)

    例１の3543と3のときのように、
    うしろから最後まで見切って3543について考えるとする。
    このとき、、
    ・端までとるU_5：U=3543
    ・右端の3だけのU_4：U=354
    ・543のU_1：U=3
    の３パターンで余りを0にしうる
    みたいなかたち
    """
    curr = 0
    for i in range(N):
        curr = int(S[N-1-i]) * pow(10, i, P) + curr
        curr %= P
        ans += mod_P[curr]
        mod_P[curr] += 1
    print(ans)
### BUGGY CODE ###

import bisect

def main():
    N = int(input())
    L = [int(i) for i in input().split()]

    L.sort()
    ans = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            tmp = L[i] + L[j]
            insert_index = bisect.bisect_left(L[j+1:], tmp)
            #print(insert_index)
            ans += insert_index

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect
import time

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    #N = 2000
    #L = [int(i) for i in range(N)]

    L.sort()
    ans = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            #ans += bisect.bisect_left(L[j+1:], L[i]+L[j])
            index = bisect.bisect_left(L, L[i]+L[j])
            ans += (index - (j+1))

    print(ans)


if __name__ == "__main__":
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")