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

import math

N = int(input())
a = list(map(int,input().split()))
a_odds = []
a_even = []

for i in range(N):
    if a[i]%2 != 0:
        a_odds.append(a[i])
    else:
        a_even.append(a[i])

a_odds.sort()
a_odds.reverse()
a_even.sort()
a_even.reverse()

count = 0
alist = []
num= 0
if a_odds!=[] and a_even!=[]:
    num = max(a_odds[0],a_even[0])
elif a_odds ==[]:
    num= a_even[0]
elif a_even == []:
    num = a_odds[0]
    
for i in range(round(math.log2(num))+1,0,-1):
    alist.append(2**i)


def my_index(l,x,default=False):
    if x in l:
        return l.index(x)
    else:
        return default

def judge(a,b):
    n = a+b
    ans = -1
    while(n>0):
        if n==1:
            ans = 0
            break
        elif n%2 == 1:
            ans = 1
            break
        elif n%2 == 0:
            n = n/2
    return ans


'''while(a_odds!=[]):
    for i in range(len(a_odds)):
        if judge(a_odds[0],a_odds[i])==0 and i!=0:
            count += 1
            a_odds.pop(i)
            break
    a_odds.pop(0)'''

while(a_odds!=[]):
    temp = a_odds[0]
    a_odds.pop(0)
    if a_odds ==[]:
        break
    for i in alist:
        b = i-temp
        if (i-temp) in a_odds:
            count += 1
            a_odds.pop(a_odds.index(i-temp))
            break
    
    
while(a_even!=[]):
    temp = a_even[0]
    a_even.pop(0)
    if a_even==[]:
        break
    for i in alist:
        if (i-temp) in a_even:
            count += 1
            a_even.pop(a_even.index(i-temp))
            break
    

print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1
twins = []
now = 1
while now <= a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, -1, -1):
    tmpa = 0
    if  b[a[i]] == 0:
        continue
    for j in range(len(twins) - 1, -1, -1):
        if twins[j] <= a[i]:
            break
        tmpa = twins[j] - a[i]
    if tmpa == a[i]:
        if b[tmpa] >= 2:
            b[tmpa] -= 2
    elif tmpa in b and b[tmpa] != 0:
        b[tmpa] -= 1
        b[a[i]] -= 1
countb = 0
for i in b:
    countb += b[i]
print((n - countb) // 2)
### BUGGY CODE ###

import bisect

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

for i in range(m):
    bc[i] = list(map(int, input().split()))

bc.sort(key=lambda x: x[0])
idx = bisect.bisect_left(a, bc[m - 1][0])

new = a

for i in range(m):
    new.extend([bc[i][1]] * bc[i][0])

new.sort()
ans = 0
n_len = len(new)

for i in range(n_len - 1, n_len - n - 1, -1):
    ans += new[i]

print(ans)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

for i in range(m):
    bc[i] = list(map(int, input().split()))

a.sort()
bc = sorted(bc, key=lambda x: -x[1])
new = []

cnt = 0

for e in bc:
    new += [e[1]] * e[0]
    cnt += e[0]

    if (n <= cnt):
        break

for i in range(min(n, cnt)):
    a[i] = max(a[i], new[i])

print(sum(a))
### BUGGY CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                s=0
                for i in range(n):
                    s+=z[i]
                    if s>=k:
                        ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                        break
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

import sys

s = int(input())
#print(s)

N=10000
d=[0]*N


for i in range(N):
  d[i]=i**5
  
for i in range(N):
  for j in range(i,N):
    if (d[i] + d[j] == s) :
      print(i,-j)
      sys.exit
    elif (d[i] - d[j] == s):
      print(i,j)
      sys.exit
    elif (d[j] + d[i] == s):
      print(j,-i)
      sys.exit
    elif (d[j] - d[i] == s):
      print(j,i)
      sys.exit

### FIXED CODE ###

import sys

s = int(input())
#print(s)

N=1000
d=[0]*N


for i in range(N):
  d[i]=i**5
  
for i in range(N):
  for j in range(i,N):
    if (d[i] + d[j] == s) :
      print(i,-j)
      sys.exit
    elif (d[i] - d[j] == s):
      print(i,j)
      sys.exit
    elif (d[j] + d[i] == s):
      print(j,-i)
      sys.exit
    elif (d[j] - d[i] == s):
      print(j,i)
      sys.exit
### BUGGY CODE ###

N=int(input())
K=[int(n) for n in input().split()]

total=0
for i in range(N):
  total+=K[i]*sum(K[i+1:])
print(total %(10**9+7))

### FIXED CODE ###

N=int(input())
K=[int(n) for n in input().split()]
S=sum(K)
total=0
for i in range(N):
  S-=K[i]
  total+=K[i]*S
print(total %(10**9+7))
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[input() for __ in range(M)]

for bc in BC:
    b,c=map(int,bc.split())
    l=[c]*b
    A.extend(l)
    A.sort(reverse=True)
    A=A[:N]

print(sum(A))


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for __ in range(M)]
BC.sort(key=lambda x: x[1],reverse=True)

l=[]
for b,c in BC:
    if len(l)+b>N:
        l.extend(list([c]*b))
        break
    else:
        l.extend(list([c]*b))
A.extend(l)
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    S = input().rstrip()
    T = input().rstrip()

    # dp[i][j] = sのi番目とtのj番目まででえられる最長部分列の長さ
    dp = [[(0, "")] * (len(T) + 1) for _ in range(len(S) + 1)]

    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            # 一致するとき
            if s == t:
                # 一致する文字の一つ左側までの最大部分列に一致した文字を加える
                if dp[i][j][0] < dp[i-1][j-1][0] + 1:
                    dp[i][j] = (dp[i-1][j-1][0] + 1, dp[i-1][j-1][1] + s)
            # 一致しない場合も、一つ手前の文字までの最大文字列を引き継ぐ
            if dp[i][j][0] < dp[i-1][j][0]:
                dp[i][j] = dp[i-1][j]
            if dp[i][j][0] < dp[i][j-1][0]:
                dp[i][j] = dp[i][j-1]
    print(dp[len(S)][len(T)][1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    S = input().rstrip()
    T = input().rstrip()

    # dp[i][j] = sのi番目とtのj番目まででえられる最長部分列の長さ
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

    # 最長部分列の長さを探索
    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            # 一致するとき
            if s == t:
                # 一致する文字の一つ左側までの最大部分列に一致した文字を加える
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
            # 一致しない場合も、一つ手前の文字までの最大文字列を引き継ぐ
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

    # 最長だった場合の具体例を復元する
    i, j = len(S), len(T)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)

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

import numpy as np
i = input()
N = list(map(int, input().split(' ')))
def one_turn(l):
  l.sort()
  n = l[0]
  
  return np.array([n]+[ i-n for i in l[1:] if i%n != 0])

if len(set(N)) == 1 :
  print(N[0])
else :
  N = np.array(N)
  while True :
    N = one_turn(N)
    if N[0] == 1 :
      print(1)
      break
    if len(N) == 1 :
      print(N[0])
      break

### FIXED CODE ###

import numpy as np
i = input()
N = list(set(map(int, input().split(' '))))
def one_turn(l):
  l.sort()
  n = l[0]
  return np.array(list(set([n]+[ l[i]%n for i in range(1,len(l)) if ((l[i]%n != 0))])))

if len(set(N)) == 1 :
  print(N[0])
else :
  N = np.array(N)
  while True :
    N = one_turn(N)
    if N[0] == 1 :
      print(1)
      break
    if len(N) == 1 :
      print(N[0])
      break
### BUGGY CODE ###

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

#max_xor = 1 << (len(bin(max(A))) - 2)
ans = N
for l in range(N-1):
    csum = A[l]
    cxor = A[l]
    for r in range(l+1,N):
        #if csum >= max_xor:
        #    break
        csum += A[r]
        cxor ^= A[r]
        if csum == cxor:
            ans += 1
        else:
            break
print(ans)


### FIXED CODE ###

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

    if N == 1:
        return 1

    ans = N
    l = 0
    r = 0
    s = A[l]
    while l < N-1:
        if r+1 < N:
            if s & A[r+1] == 0:
                r += 1
                s |= A[r]
                ans += r - l
                continue
        if l == r:
            l += 1
            r += 1
            s = A[l]
        else:
            s &= ~A[l]
            l += 1
    return ans

print(solve())

#  1  2  4  8  1
#  l  r              (1,2)
#  l     r           (1,4)(2,4)
#  l        r        (1,8)(2,8)(4,8)
#     l     r
#     l        r     (2,1)(4,1)(8,1)
### BUGGY CODE ###

from pprint import pprint
import numpy as np
n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]

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


for i in range(n):
      #print("重さ：{}".format(wsum))
  for wsum in range(1,w+1):
    #print("i={}".format(i))
    if wsum >= wv[i][0]:
        #print("選ぶ, (重さ：{}, 価値：{})".format(wl[i], vl[i]))
        dp[i][wsum] = max(dp[i-1][wsum], dp[i-1][wsum-wv[i][0]]+wv[i][1])
    else:
      dp[i][wsum] = dp[i-1][wsum]
    #pprint(dp)

dp=np.array(dp)
print(np.max(dp))
      

### FIXED CODE ###

from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  #print(dp)
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)
### BUGGY CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    # n = int(input())
    # a = readInt()
    n = 200000
    a = [1000000000 for i in range(n)]
    ans = 0
    for i in range(n-1):
        for j in range(i+1,n):
            ans += a[i] * a[j]
            ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()



### FIXED CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    a = readInt()
    c_sum = [0]
    for i in range(n):
        c_sum.append(c_sum[i]+a[i])
    ans = 0
    for i in range(n-1):
        ans += a[i] * (c_sum[-1] - c_sum[i+1])
        ans %= mod
    print(ans)
    return

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

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []
for i in range(len(a)):
    for j in range(len(b)):
        d.append(a[i]+b[j])
tmp = sorted(d, reverse=True)
if len(tmp) < k:
    use_tmp = tmp
else:
    use_tmp = tmp[0:k]
    
ans = []
for i in range(len(use_tmp)):
    for j in range(len(c)):
        ans.append(use_tmp[i]+c[j])
final_ans = sorted(ans, reverse=True)

for i in range(k):
    print(final_ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

sumAB = sorted([ai + bi for ai in a for bi in b],reverse=True)[:k]
final_ans = sorted([ci + abi for ci in c for abi in sumAB],reverse = True)[:k]

for i in range(k):
    print(final_ans[i])
### BUGGY CODE ###

import numpy as np

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

# dp = [0]*(ww+1)
dp = np.zeros(ww+1)

for i in range(n):
    w,v = map(int, input().split())
    for j in range(ww-w+1)[::-1]:
        if dp[j] or j==0:
            dp[j+w] = max(dp[j+w], dp[j]+v)
print(int(max(dp)))

### FIXED CODE ###

import numpy as np

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

dp = np.zeros(ww+1)

for i in range(n):
    w,v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w]+v)

print(int(max(dp)))
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(0,N):
    for j in range(i,N):
        if S[i] != S[j]:
            str = 'RGB'.replace(S[i],'').replace(S[j],'')
            ans += S.count(str, j+1, N+1)
            if j+j-i < N:
                if S[j+j-i] == str:
                    ans -=1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

# それぞれ違う文字の組み合わせの数
ans = S.count('R')*S.count('G')*S.count('B')

# j-i!=k-jの組み合わせ
for i in range(0, N-2):
    for j in range(i+1, N-1):
        k = j+j-i
        if k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ans -= 1

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

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append((c,b))
tmp_li.sort(reverse=True)
#print(tmp_li)
""" for c,b in tmp_li:
    li.extend([c]*b)
    if len(li)>= 2*n:
        break
li.sort(reverse=True)
print(sum(li[:n])) """

count = 0
for c,d in tmp_li:
    kazu = min(d,n-count+1)
    li.extend([c]*kazu)
    if count>=n:
        break
li.sort(reverse=True)
print(sum(li[:n]))

### FIXED CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append((c,b))
tmp_li.sort(reverse=True)
#print(tmp_li)
for c,b in tmp_li:
    li.extend([c]*b)
    if len(li)>= 2*n:
        break
li.sort(reverse=True)
print(sum(li[:n]))
### BUGGY CODE ###

import bisect
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
listofmax = [A[0]]
for j in range(1, N):
    if listofmax[0] >= A[j]:
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]
print(len(listofmax))


### FIXED CODE ###

import bisect
from collections import deque
de1 = deque()
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
de1.appendleft(A[0])
for j in range(1, N):
    if de1[0] >= A[j]:
        de1.appendleft(A[j])
    else:
        de1[bisect.bisect_left(de1, A[j]) - 1] = A[j]
print(len(de1))
### BUGGY CODE ###

from collections import defaultdict

n, m = [int(i) for i in input().split()]

A = defaultdict(int)
p = 10 ** 9 + 7

i = 2

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

while m % i == 0:
    m //= i
    A[i] += 1

i += 1

while m != 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 2

n -= 1
ans = 1

for v in A.values():
    ans *= f[v+n] * invf[n] * invf[v] % p
    ans %= p

print(ans)

### FIXED CODE ###

import math
from collections import defaultdict

n, m = [int(i) for i in input().split()]

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)
    exit()

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2

while m != 1 and i <= math.sqrt(m) + 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

if m != 1:
    A[m] = 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

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

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort(reverse=True)

for a, aa in enumerate(li):
  if a < n - 2:
    for b, bb in enumerate(li[a+1:]):
      for cc in li[a+1+b+1:]:
        if bb + cc <= aa:
          break
        if aa < bb + cc and bb < cc + aa and cc < aa + bb:
          ans += 1
            
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort()

for i in range(n):
  for j in range(i+1, n):
    cnt = bisect.bisect_left(li, li[i]+li[j])
    ans += cnt - j - 1
            
print(ans)
### BUGGY CODE ###

import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
i=0
while i<n:
    s=l[n-i-1]
    b=1
    while b<=s:
        b*=2
    g=b-s
    p=bisect.bisect_left(l[:n-i-1],g)
    if p==n-i-1:
        i+=1
        continue
    else:
        if l[p]==g:
            l.pop(n-i-1)
            l.pop(p)
            i+=2
            ans+=1
        else:
            i+=1
print(ans)


### FIXED CODE ###

from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)
### BUGGY CODE ###

from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
input = sys.stdin.readline

start = time.time()
N = int(input())
A = list(map(int, input().split(' ')))
Asum = [i+A[i] for i in range(N)]
Adif = [i-A[i] for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if Asum[i] == Adif[j]:
            ans += 1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
input = sys.stdin.readline

start = time.time()
N = int(input())
A = list(map(int, input().split(' ')))
Asum = [i+A[i] for i in range(N)]
Adif = [i-A[i] for i in range(N)]

ans = 0
d = defaultdict(int)
for i in range(N):
    ans += d[Adif[i]]
    d[Asum[i]] += 1

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

import collections

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

s_count_list = [collections.Counter(S) for S in s]

counted = []
count = 0
for s_count in s_count_list:
    if s_count not in counted:
        n = s_count_list.count(s_count)
        counted.append(s_count)
        count += n * (n - 1) // 2
            
print(count)

### FIXED CODE ###

import collections
import sys

N = int(input())
s = [sorted(collections.Counter(sys.stdin.readline().rstrip()).items()) for _ in range(N)]

counted = {}
for s_count in s:
    if str(s_count) not in counted:
        counted[str(s_count)] = 1
    else:
        counted[str(s_count)] += 1


count = 0        
for n in counted.values():
    count += n * (n - 1) // 2
            
print(count)
### BUGGY CODE ###

def solve():
  x,y,z,k = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  b = list(int(i) for i in input().split())
  c = list(int(i) for i in input().split())
  a = sorted(a,reverse=True)
  b = sorted(b,reverse=True)
  c = sorted(c,reverse=True)
  ab = []
  abc = []
  
  for i in range(x):
    for j in range(y):
      ab.append(a[i]+b[j])
  ab = sorted(ab,reverse = True)
  for t in range(min(k,len(ab))):
    for l in range(z):
      abc.append(ab[t]+c[l])
      
  abc = sorted(abc,reverse = True)
  for i in range(k):
    print(abc[i])

solve()

### FIXED CODE ###

def solve():
  x,y,z,k = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  b = list(int(i) for i in input().split())
  c = list(int(i) for i in input().split())
  a = sorted(a,reverse=True)
  b = sorted(b,reverse=True)
  c = sorted(c,reverse=True)
  ab = []
  abc = []
  
  for i in range(x):
    for j in range(y):
      ab.append(a[i]+b[j])
  ab = sorted(ab,reverse = True)
  for t in range(min(k,len(ab))):
    for l in range(z):
      abc.append(ab[t]+c[l])
      
  abc = sorted(abc,reverse = True)
  for i in range(k):
    print(abc[i])

solve()