Harryxun/sft_time huggingface dataset:
### 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()))

AB=[0]*(x*y)
i=0
for a in A:
    for b in B:
        AB[i]=a+b
        i+=1

AB=sorted(AB,reverse=True)[:min(k,x*y)]
ABC=[0]*(min(k,x*y)*z)
i=0
for ab in AB:
    for c in C:
        ABC[i]=ab+c
        i+=1

ABC=sorted(ABC,reverse=True)[:k]

for abc in ABC:
    print(abc)


### FIXED 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()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


AB=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:min(k,x*y)] for c in C]
ABC.sort(reverse=True)

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

from collections import deque
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())
ans=0
for x in range(h):
    for y in range(w):
        if s[x][y]=='.':
            continue
        path = deque([[x,y]])
        sc=[[0 for i in range(w)] for j in range(h)]
        sc[x][y]=1
        while len(path)>0:
            p = path.popleft()
            i,j=p[0],p[1]
            tc = '.' if s[i][j] == '#' else '#'
            point = 1 if s[i][j] == '#' else 0
            if i > 0 and s[i-1][j]==tc and sc[i-1][j]==0:
                sc[i-1][j]=1
                path.append([i-1,j])
                ans += point
            if j > 0 and s[i][j-1]==tc and sc[i][j-1]==0:
                sc[i][j-1]=1
                path.append([i,j-1])
                ans += point
            if i < h-1 and s[i+1][j]==tc and sc[i+1][j]==0:
                sc[i+1][j]=1
                path.append([i+1,j])
                ans += point
            if j < w-1 and s[i][j+1]==tc and sc[i][j+1]==0:
                sc[i][j+1]=1
                path.append([i,j+1])
                ans += point
#print(sc)
print(ans)

### FIXED CODE ###


from collections import deque
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())
ans=0        
sc=[[0 for i in range(w)] for j in range(h)]

for x in range(h):
    for y in range(w):
        if s[x][y]=='.' or sc[x][y]==1:
            continue
        path = deque([[x,y]])
        sc[x][y]=1
        b=1
        wh=0
        while len(path)>0:
            p = path.popleft()
            i,j=p[0],p[1]
            tc = '.' if s[i][j] == '#' else '#'
            point = b if s[i][j] == '#' else wh           
            if i > 0 and s[i-1][j]==tc and sc[i-1][j]==0:
                sc[i-1][j]=1
                path.append([i-1,j])
                if s[i-1][j] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if j > 0 and s[i][j-1]==tc and sc[i][j-1]==0:
                sc[i][j-1]=1
                path.append([i,j-1])
                if s[i][j-1] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if i < h-1 and s[i+1][j]==tc and sc[i+1][j]==0:
                sc[i+1][j]=1
                path.append([i+1,j])
                if s[i+1][j] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if j < w-1 and s[i][j+1]==tc and sc[i][j+1]==0:
                sc[i][j+1]=1
                path.append([i,j+1])
                if s[i][j+1] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
print(ans)
### BUGGY CODE ###

def main():
    N_ko, K_kai = map(int, input().split())
    init_light = list(map(int, input().split()))


    for k in range(K_kai):
        light_list = [0 for i in range(N_ko)]

        for i in range(N_ko):
            left = max(0, i - init_light[i])
            right = min(N_ko - 1, i + init_light[i])
            
            light_list[left] += 1

            if (right + 1 < N_ko):
                light_list[right + 1] -= 1
            
        for i in range(1, N_ko):
            light_list[i] += light_list[i - 1]
        
        init_light = light_list

        judge = all([init_light[i] == N_ko for i in range(N_ko)])
        
        
        if (judge):
            break   
    
    print(' '.join(map(str,light_list)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N_ko, K_kai = map(int, input().split())
    init_light = list(map(int, input().split()))


    for k in range(min(42,K_kai)):
        light_list = [0 for i in range(N_ko)]

        for i in range(N_ko):
            left = max(0, i - init_light[i])
            right = min(N_ko - 1, i + init_light[i])
            
            light_list[left] += 1

            if (right + 1 < N_ko):
                light_list[right + 1] -= 1
            
        for i in range(1, N_ko):
            light_list[i] += light_list[i - 1]
        
        init_light = light_list

    
    print(' '.join(map(str,light_list)))


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


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
# input = sys.stdin.readline



M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in st()]
 



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
d = {}
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    if (i, par, black) in d:return d[(i, par, black)]
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    d[(i, par, black)] = ans
    return ans



n = val()
g = [set() for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

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

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

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d) * n * n * cmb(n * m - 2, k - 2)) % mod
    return ret

print((doit(n, m, k) + doit(m, n, k)) % mod)

### FIXED CODE ###

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

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d) * n * n * cmb(n * m - 2, k - 2)) % mod
    return ret

print((doit(n, m, k) + doit(m, n, k)) % mod)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input())-1)  
    
index = 0
count = 0
flag = True
check = []
while flag:
    index = A[index]
    check.append(index)
    count += 1
    if len(list(set(check))) != len(check):
        flag = False
        count = -1
    if index == 1:
        flag = False
print(count)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input())-1)  
    
index = 0
count = 1
flag = True
while flag:
    index = A[index]
    if index == 1:
        flag = False
    else:
        count += 1
    if count > N:
        flag = False
        count = -1
print(count)
### BUGGY CODE ###

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

ch = 1
ind = 0
bits = [ch]
while ch*2 <= K:
    ind += 1
    ch *= 2
    bits.append(ch)

#print(ch,ind)
#ch_max = 2**(ind+1) -1
#print(ch_max)

tmp = [0 for _ in range(ind+1)]

for a in A:
    for i,bit in enumerate(bits):
        if a & bit:
            tmp[i] = tmp[i] + 1
#print(tmp)

ans_x = 0
for i,t in enumerate(tmp):
    if 2*t < N and K > 0:# and ans_x + bits[i] <= K:
        ans_x += bits[i]
#        print('koko')
    else:
        ans_x += 0
#        print(bits[i])

ans = 0
if ans_x <= K:
    for n in range(N):
        ans += ans_x ^ A[n]
else:
    ans_max = 0
    for i in range(K-bits[-1],K+1):
        ans_tmp = 0
        for n in range(N):
            ans_tmp += i ^ A[n]
        ans_max = max(ans_tmp,ans_max)

    ans = ans_max

    # for i in range(ans_x - bits[-1],K+1):
    #     ans_x2 = i
    #     ans_tmp = 0
    #     for n in range(N):
    #         ans_tmp += ans_x2 ^ A[n]
    #     ans_max = max(ans_max, ans_tmp)

    # ans = ans_max

print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/abc117/submissions/4165407
n,k=map(int,input().split())
a=list(map(int,input().split()))
t,ans=2**40,0
while t:
    c=sum([(a[i]&t)//t for i in range(n)])
    if k<t or c*2>=n:
        ans+=t*c
    else:
        ans+=t*(n-c)
        k -= t
    t //= 2

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

import itertools
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
res = 0
for i in range(N-2):
    if L[i] < L[i+1] + L[i+2]:
        comb_list = itertools.combinations(L[i+1:], 2)
        res +=  sum([L[i] < (comb[0] + comb[1]) for comb in comb_list])
    else: continue
print(res)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
l = list(map(int, input().split()))
l.sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        t = l[i] + l[j]
        idx = bisect_left(l, t)
        res += idx-j-1
print(res)
### BUGGY CODE ###

n,k = map(int,input().split())
sai = list(map(int,input().split()))
kk = []
for x in range(len(sai)):
    sai[x] = ((sai[x]+1)*sai[x])/2/sai[x]
for y in range(n-k+1):
    kk.append(sum(sai[y:y+k]))
print(max(kk))

### FIXED CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
li = list(map(lambda x:(x+1)/2,li))

wk = 0
nn = n-k

for i in range(0,k):
    wk += li[i]
kwk = wk
for j in range(nn):
    wk = wk - li[j]
    wk = wk + li[j+k]
    kwk = max(wk,kwk)
 
print(kwk)
### BUGGY CODE ###

k,s=map(int,input().split())

val=list(range(0, k+1))
n=len(val)
ans=0

for i in range(n):
    if val[i]>s:
        break
    for j in range(n):
        if val[i]+val[j]>s:
            break
        if s-(val[i]+val[j]) in val:
            ans+=1
            continue
print(ans)


### FIXED CODE ###

k, s=map(int, input().split())

ans=0
for x in range(0, k+1):
    if x>s:
        break
    for y in range(0, k+1):
        if x+y>s:
            break
        z=s-x-y
        if 0<=z and z<=k:
            ans+=1
            continue
print(ans)
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i
xy.sort()
y = [xy[i][1] for i in range(N)]

mod = 998244353
p2 = [1]*(N+1)
for i in range(N):
    p2[i+1] = p2[i]*2%mod

bit = BIT(N)

ans = 0

for i in range(N):
    bit.add(y[i],1)
    n1 = i+1-bit.sum(y[i])
    n2 = i-n1
    n3 = N-y[i]-1-n1
    n4 = N-i-1-n3
    ans += 1
    ans += (p2[n1]-1)+(p2[n2]-1)+(p2[n3]-1)+(p2[n4]-1)
    ans += (p2[n1]-1)*(p2[n2]-1)+(p2[n3]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)+(p2[n2]-1)*(p2[n4]-1)+2*(p2[n1]-1)*(p2[n4]-1)+2*(p2[n2]-1)*(p2[n3]-1)
    ans += 2*((p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)+(p2[n1]-1)*(p2[n2]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)*(p2[n4]-1)+(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1))
    ans += 2*(p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1)
    ans %= mod
print(ans)

### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

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

def main():
    n = int(input())
    a = list(map(int, input().split()))

    m = 0
    for i in range(n):
        dis = 0
        bef = 0
        if i != 0:
            if abs(a[i-1]) <= b and b <= abs(a[i+1]):
                print(m)
                continue;
        for idx, b in enumerate(a):
            if idx == i:
                continue
            dis += abs(bef - b)
            bef = b
        dis += abs(bef)
        if dis > m:
            m = dis
        print(dis)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    n = int(input())
    a = list(map(int, input().split()))

    dis = 0
    bef = 0
    for b in a:
        dis += abs(bef - b)
        bef = b
    dis += abs(bef)
    for i in range(n):
        m = 0 if i == 0 else a[i-1]
        l = 0 if i == len(a) - 1 else a[i+1]
        print(dis - (abs(m - a[i]) + abs(a[i] - l) - abs(m - l)))

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

N = int(input())

A = list(map(int, input().split()))
max_count = 0
lower = min(A)-1
upper = max(A)+1
for i in range(lower,upper+1):
    count = 0
    for j in range(N):
        for k in range(-1,2,1):
            if A[j] + k == i:
                count += 1
    max_count = max(count, max_count)
    
print(max_count)

### FIXED CODE ###

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

max_count = 0

L = [0]*10**5
for i in A:
    L[i] += 1

for i in range(10**5+1):
    count = 0
    for j in range(-1,2):
        if i+j >= 0 and i+j < 10**5:
            count += L[i+j]
    max_count = max(count, max_count)
print(max_count)
### BUGGY CODE ###

import sys
MX = 10**6
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    C = [0] * (MX + 1)
    for a in A:
        C[a] += 1
    ans = 0
    for a in A:
        if C[a] >= 2: continue
        for d in dv(a):
            if C[d] > 0:
                break
        else:
            ans += 1
    print(ans)

def dv(x):
    res = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            res.append(i)
            res.append(x // i)
    if x != 1:
        res.append(1)
    return res

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    w = [0] * (10 ** 6 + 1)
    for a in A:
        w[a] += 1
    f = [False] * (10 ** 6 + 1)
    for a in A:
        if f[a]:
            w[a] = 0
            continue
        for b in range(a * 2, 10 ** 6 + 1, a):
            w[b] = 0
        f[a] = True
    print(sum(w))

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

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] + [0]*3 for i in range(10) }
d["?"] = [1] * 10 + [0]*3
l = d[S[-1]] + [0]*3

for i, s in enumerate(S[-2::-1]):
  l = [(sum([l[(k-j*10**(i+1))%13] * d[s][j] for j in range(13)]))%N for k in range(13)]
  #print(l)
print(l[5])         

### FIXED CODE ###

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[0]] + [0]*3
#print(l)
for i in range(1, len(S)):
  if S[i] == "?":
    l = [(sum([l[((k - j) * 4)%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[((k - int(S[i])) * 4)%13] for k in range(13)]
  #print(l)
print(l[5])
### BUGGY CODE ###

import bisect
n,k=map(int,input().split())
a=[]
for i in range(n):
    p=int(input())
    a.append(p-k)
d=[0]
for i in range(n):
    d.append(d[-1]+a[i])
d.reverse()
ans=0
b=[d[0]]
for i in range(n):
    bi=bisect.bisect_left(b,d[i+1])
    ans+=(i+1)-bi
    bisect.insort(b,d[i+1])
print(ans)

### FIXED CODE ###

import bisect
#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,k=map(int,input().split())
num=2**(n).bit_length()
seg=[ide_ele]*2*num
a=[]
for i in range(n):
    p=int(input())
    a.append(p-k)
d=[0]
for i in range(n):
    d.append(d[-1]+a[i])
b=sorted(d)
a=[]
for i in d:
    p=bisect.bisect_left(b,i)
    a.append(p)
#init(p)
ans=0
a.reverse()
update(a[0],1)
for i in range(n):
    ans+=query(a[i+1],1+n)
    update(a[i+1],query(a[i+1],a[i+1]+1)+1)
print(ans)
#query(0,i)

exit()
### BUGGY CODE ###

from collections import deque
def bfs(start):
    global count
    d = [float('inf') for i in range(N)]
    d[start] = 0
    que = deque()
    que.append(start)
    alr = [start]
    while que:
        q = que.popleft()
        c = d[q]
        for i in path[q]:
            if i not in alr:
                que.append(i)
                alr.append(i)
                d[i] = c+1
    for i in range(start+1,N):
        count[d[i]-1] += 1

N,X,Y = map(int,input().split())
path = [[] for i in range(N)]
path[0] = [1]
path[N-1] = [N-2]
for i in range(1,N-1):
    path[i] = [i-1,i+1]
path[X-1].append(Y-1)
path[Y-1].append(X-1)

count = [0 for i in range(N-1)]
for i in range(N-1):
    bfs(i)
for i in range(N-1):
    print(count[i])

### FIXED CODE ###

N,X,Y = map(int,input().split())
ans = [0 for i in range(N-1)]
for i in range(1,N):
    for j in range(i+1,N+1):
        mina = min(j-i, abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(X-j))
        ans[mina-1] += 1
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for low in range(N-2):
    for mid in range(low+1,N-1):
        for hi in range(N-1,mid,-1):
            if L[hi] < L[low] + L[mid]:
                ans += (hi - mid)
                break
print(ans)

### FIXED CODE ###

from itertools import *
N = int(input())
L = list(map(int,input().split()))
csum = list(0 for _ in range(2000+1))
for i in range(N): csum[L[i]] += 1
csum = list(accumulate(csum))
ans = 0
for ib in range(N):
    for ia in range(ib):
        a, b = L[ia], L[ib]
        minL, maxL = abs(a-b), a+b
        ans += csum[maxL-1] - csum[minL]
        if minL < a and a < maxL: ans -= 1
        if minL < b and b < maxL: ans -= 1
print(ans//3)
### BUGGY CODE ###

N, M = map(int, input().split())

pairs = [[0] for _ in range(N + 1)]
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0 for _ in range(N + 1)]
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了

n = 1
while n_ans < N - 1:
    for m in pairs[n]:
        if m != 0 and m != 1:
            if ans[m] == 0:
                ans[m] = n
                n_ans += 1

    n = m

print('Yes')
for i in range(2, N + 1):
    print(ans[i])

### FIXED CODE ###

N, M = map(int, input().split())

pairs = [[] for _ in range(N + 1)]  # pairs[i]:iと直接つながっている部屋のリスト
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0 for _ in range(N + 1)]
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了
done = [False for _ in range(N + 1)]  # 探索済リスト
todo = [1]

while n_ans < N - 1:
    for n in todo:
        for m in pairs[n]:
            if not done[m]:
                done[m] = True
                ans[m] = n
                n_ans += 1
                todo.append(m)

print('Yes')
for i in range(2, N + 1):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
inp_ls = input().split(" ")
a_ls = [int(e) for e in inp_ls[:n]]

cnt = 0
for i in range(n-1):
	abs_val = i+1
	for j in range(n-abs_val):
		if a_ls[j] + a_ls[j+abs_val] == abs_val: cnt += 1

print(cnt)

### FIXED CODE ###

def count_j(arg_ls, th, b_idx, e_idx):
	if b_idx-1 == e_idx: return 0
	if b_idx == e_idx: return int(arg_ls[b_idx] > th)
	cent_idx = (e_idx+1 - b_idx) // 2 + b_idx
	cent_j = arg_ls[cent_idx]
	if cent_j > th:
		return count_j(arg_ls, th, b_idx, cent_idx-1) + (e_idx+1 - cent_idx)
	else:
		return count_j(arg_ls, th, cent_idx, e_idx)

n = int(input())
inp_ls = input().split(" ")
a_ls = [int(e) for e in inp_ls[:n]]

i_dic = {}
for i,a in enumerate(a_ls):
	val = -a+(i+1)
	if val not in i_dic: i_dic[val] = []
	i_dic[val].append(i+1)

cnt = 0
for i in range(len(a_ls)):
	val = a_ls[i] + (i+1)
	cand_ls = i_dic.get(val, [])
	result = count_j(cand_ls, (i+1), 0, len(cand_ls)-1)
	cnt += result

print(cnt)