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

import itertools
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cakes = []
for _ in range(N):
    x, y, z = map(int, input().split())
    cakes.append((x, y, z))

ans = 0
for i in itertools.combinations(cakes, M):
    sx, sy, sz = 0, 0, 0
    for j in i:
        x, y, z = j
        sx = sx + x
        sy = sy + y
        sz = sz + z
    ans = max(ans, abs(sx) + abs(sy) + abs(sz))
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
cakes = []
for _ in range(N):
    x, y, z = map(int, input().split())
    cakes.append((x, y, z))

ans = 0
for i in range(2**3):
    op1, op2, op3 = 1, 1, 1
    for idx, j in enumerate(bin(i)[2:][::-1], 1):
        j = int(j)
        if idx == 1:
            op1 = 1 if j == 0 else -1
        elif idx == 2:
            op2 = 1 if j == 0 else -1
        elif idx == 3:
            op3 = 1 if j == 0 else -1
            
    cakes.sort(reverse=True, key=lambda x: op1 * x[0] + op2 * x[1] + op3 * x[2])
    sx, sy, sz = 0, 0, 0
    for cake in cakes[:M]:
        sx += cake[0]
        sy += cake[1]
        sz += cake[2]
    ans = max(ans, abs(sx) + abs(sy) + abs(sz))
print(ans)
### BUGGY CODE ###

import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# lst_weight = [0 for _ in range(N)]
# lst_value = [0 for _ in range(N)]
# for i in range(N):
#     lst_weight[i], lst_value[i] = map(int, input().split())

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

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

for i in range(N):
    weight, value = map(int, input().split())
    for sum_w in range(W+1):
        # i番目の品物を選ぶ
        if sum_w - weight >= 0:
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w - weight] + value)
        # i番目の品物を選ばない
        dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

### FIXED CODE ###


import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
score=1
for i in range(k):
  score=score*a[i]
for i in range(k,n):
  rscore=score
  score=score*a[i]/a[i-k]
  if score>rscore:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k,n):
  if a[i]/a[i-k]>1:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    X, Y, Z, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))
    AB = [a+b for (a,b) in list(itertools.product(A,B))]
    AB.sort(reverse=True)
    ans = [ab + c for (ab,c) in list(itertools.product(AB[:K],C))]
    ans.sort(reverse=True)
    for i in range(K):
        print(ans[i])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import itertools
readline = sys.stdin.buffer.readline

X, Y, Z, K = map(int, readline().split())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
C = list(map(int, readline().split()))
AB = [a+b for (a,b) in list(itertools.product(A,B))]
AB.sort(reverse=True)
ans = [ab + c for (ab,c) in list(itertools.product(AB[:K],C))]
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    #初期値は0
    def Num(dest,flog,h):
        q=dest-1
        if flog[q]>0:
            return flog[q]
        if dest<k+2:
            res=abs(h[q]-h[0])
            flog[q]=res
            return res
        
        min=Num(q,flog,h)+abs(h[q]-h[q-1])
        for i in range(2,k+1):
            tmp=Num(dest-i,flog,h)+abs(h[q]-h[q-i])
            if min>tmp:
                min=tmp
        flog[q]=min
        return min   
    print(Num(n,flog,h))
if __name__=="__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    for i in range(n):#dest=i 0が１
        if i<k+1:#0~k
            flog[i]=abs(h[i]-h[0])
        else:
            min=10**9
            for j in range(1,k+1):#1~k
                tmp=flog[i-j]+abs(h[i]-h[i-j])
                if tmp<min:
                    min=tmp
            flog[i]=min
    print(flog[n-1])
   # print(flog)
if __name__=="__main__":
    main()
### BUGGY CODE ###

N = int(input())
A = [int(j) for j in input().split()]
result = 1

for a in A:
    result *=a


if result >10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N = int(input())
A = [int(j) for j in input().split()]
from collections import Counter

A_C =Counter(A)
A_C = sorted(A_C.items(),key=lambda x:-x[0])

if 0 == A_C[-1][0]:
    print(0)
    exit()
    
result = 1
for a in A_C:
    result*=(a[0]**a[1])

    if result >10**18:
        print(-1)
        exit()

print(result)
### BUGGY CODE ###

n = int(raw_input())
S = map(int, raw_input().strip().split(' '))
q = int(raw_input())
T = map(int, raw_input().strip().split(' '))

def binary_search(S,k):
    if len(S) == 0: return False
    if len(S) == 1 and S[0] != k: return False
    p = len(S)/2
    if S[p] == k: return True
    elif S[p] > k:
        return binary_search(S[:p],k)
    else:
        return binary_search(S[p:],k)

c = 0
for t in T:
    if binary_search(S,t): c += 1
print c

### FIXED CODE ###

def search(a, x):
    n = len(a)
    hi = n-1
    lo = 0
    while hi >= lo:
        med = (hi+lo)/2
        if a[med] == x:
            return True
        elif a[med] > x:
            hi = med-1
        else:
            lo = med+1
    return False

n = int(raw_input())
S = map(int, raw_input().split(' '))
q = int(raw_input())
T = map(int, raw_input().split(' '))

found = 0
for x in T:
    if search(S, x):
        found += 1

print found
### BUGGY CODE ###

import numpy as np
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
def lcma(a,b):
  return a*b//gcd(a,b)
n=int(input())
a = list(map(int, input().split()))
lcm = a[0]
for i in a[1:]:
  lcm=lcma(lcm,i)
a=np.array(a)
a=lcm//a
ans=sum(a)%(10**9+7)
print(ans)

### FIXED CODE ###

n=int(input())
import fractions
a = list(map(int, input().split()))
lcm = a[0]
for i in a:
  lcm = lcm * i // fractions.gcd(lcm, i)
b=[]
for i in a:
  b.append(lcm//i)
ans=sum(b)%(10**9+7)
print(ans)
### BUGGY CODE ###

from math import factorial
from collections import Counter

def comb(n,r):
    return factorial(n) // factorial(r) // factorial(n - r)
    
N = int(input())
A = list(map(int, input().split()))
ans = 0
cumulative_sum = [0] + [sum(A[:i+1]) for i in range(N)]
counts = Counter(cumulative_sum).most_common()
ans = 0
for c in counts:
    if c[1] < 2:
        break
    ans += comb(c[1], 2)
    
print(ans)


### FIXED CODE ###

from collections import Counter
import numpy as np

N = int(input())
A = [0]+list(map(int, input().split()))

cumulative_sum = np.cumsum(A)
counts = Counter(cumulative_sum)
ans = 0
for v in counts.values():
    ans += v * (v-1) // 2
    
print(ans)
### BUGGY CODE ###

S = input()
 
dp = [[(0,0)]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = (1,1)
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      if (dp[k-1][i][1] == 1):
        tmp = (i * 10) + l
        m = tmp % 13
        dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod, 1)
  k += 1
print(dp[k-1][5][0])


### FIXED CODE ###

S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])
### BUGGY CODE ###

a,b,x=map(int,input().split())
cnt=0
a=(a+x-1)//x*x
for i in range(a,b+1,x):
  cnt+=1
print(cnt)

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

n = input()
nums = list(map(int, input().split()))


# ある数の誤差１で収まる個数を計算する
# 最も多い物を出力
# 一度全て展開する
# 数列の最初の数について全て走査して、つぎはその次の数、、、と繰り返していく
# どこにカウンターを設置するのがよいか
# 外側にゼロでカウンターを配置して最も内側で外にあるカウンターよりも数値が大きければ入れ替える

ans = 0
for i in nums:
    cnt = 0
    for n in nums:
        if n in range(i-1, i+2):
            cnt += 1
    if ans < cnt:
        ans = cnt

print(ans)


### FIXED CODE ###

from collections import OrderedDict

n = input()
nums = list(map(int, input().split()))

number_hash = OrderedDict()

for i in sorted(nums):
    if i not in number_hash:
        number_hash[i] = 1
    else:
        number_hash[i] += 1

ans = 0
for i in number_hash:
    cnt = 0
    # 今とある定数をハッシュから引き出した
    # ハッシュの中から今取り出した数プラマイ１の数字が多い物を見つける
    i_d = i - 1
    i_u = i + 1
    if i_d in number_hash:
        cnt += number_hash[i_d]
    if i_u in number_hash:
        cnt += number_hash[i_u]
    cnt += number_hash[i]

    if ans < cnt:
        ans = cnt

print(ans)
### 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()))

l=[]
for s in a:
    for t in b:
        l.append(s+t)
l.sort()
l.reverse()
n=[]
for s in l[:k+1]:
    for t in c:
        n.append(s+t)
n.sort()
n.reverse()
for i in range(k):
    print(n[i])

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

l=[]
for s in range(x):
    for t in range(y):
        for u in range(z):
            if (s+1)*(t+1)*(u+1)<= k:
                l.append(a[s]+b[t]+c[u])
            else:
                break
l.sort(reverse=True)
for i in range(k):
    print(l[i])
### BUGGY CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    s = np.array([list(input()) for _ in range(h)])
    t = np.zeros((h+2, w+2))
    t[1:-1, 1:-1][s == "."] = 1
    row = np.zeros((h+2, w+2))
    col = row.T.copy()
    for i in range(1, h+1):
        idx = np.where(t[i] == 0)
        dif = np.diff(idx[0])
        for j in range(np.size(idx) - 1):
            L, R = idx[0][j], idx[0][j+1]
            row[i][L+1] += dif[j]-1
            row[i][R] -= dif[j]-1
        row[i] = np.cumsum(row[i])
    t = t.T
    for i in range(1, w+1):
        idx = np.where(t[i] == 0)
        dif = np.diff(idx[0])
        for j in range(np.size(idx) - 1):
            L, R = idx[0][j], idx[0][j+1]
            col[i][L+1] += dif[j]-2
            col[i][R] -= dif[j]-2
        col[i] = np.cumsum(col[i])
    col = col.T
#    for i in range(h+2):
#        print(row[i])
#    print("")
#    for i in range(h+2):
#        print(col[i])
    cost = np.add(row, col)
    print(int(np.max(cost)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    s = np.array([list(input()) for _ in range(h)])
    t = np.zeros((h+2, w+2))
    t[1:-1, 1:-1][s == "."] = 1
    row = np.zeros((h+2, w+2))
    col = np.zeros((w+2, h+2))
    for i in range(1, h+1):
        idx = np.where(t[i] == 0)[0]
        dif = np.diff(idx)
        row[i, idx[:-1]+1] += dif-1
        row[i, idx[1:]] -= dif-1
        row[i] = np.cumsum(row[i])
    t = t.T
    for i in range(1, w+1):
        idx = np.where(t[i] == 0)[0]
        dif = np.diff(idx)
        col[i, idx[:-1]] += dif-2
        col[i, idx[1:]] -= dif-2
        col[i] = np.cumsum(col[i])
    col = col.T
    cost = np.add(row, col)
    print(int(np.max(cost)))

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

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
x=1
for i in range(60):
  z=o=0
  for j in range(n):
    if a[j]%2:o+=1
    else:z+=1
    a[j]//=2
  ans+=(x*o*z)%mod
  ans%=mod
  x=(x*2)%mod
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
x=1
for i in range(60):
  z=o=0
  for j in range(n):
    if a[j]%2:o+=1
    else:z+=1
    a[j]//=2
  ans+=(x*o*z)%mod
  ans%=mod
  x=(x*2)%mod
print(ans)
### BUGGY CODE ###

import heapq as hq

x,y,z,k = map(int,input().split())
a = list(map(lambda x:int(x) * (-1),input().split()))
b =list(map(lambda x:int(x) * (-1),input().split()))
c = list(map(lambda x:int(x) * (-1),input().split()))
a.sort()
b.sort()
c.sort()
possibles = [(a[0]+b[0]+c[0],0,0,0)]

done = [[[0 for _ in range(z)]for _ in range(y)] for _ in range(x)]
done[0][0][0] = 1
def neibor(ai,bi,ci,possibles,done):
    for aj,bj,cj in [(ai+1,bi,ci),(ai,bi+1,ci),(ai,bi,ci+1)]:
        if (aj<=x-1) and (bj<=y-1) and (cj<=z-1) and (not done[aj][bj][cj]):
            hq.heappush(possibles,(a[aj]+b[bj]+c[cj],aj,bj,cj))
            done[aj][bj][cj] = 1
    

def conf(possibles,done):
    yam,ai,bi,ci = hq.heappop(possibles)
    print(-1*yam)
    neibor(ai,bi,ci,possibles,done)

for i in range(k):
    yam,ai,bi,ci = hq.heappop(possibles)
    print(-1*yam)
    for aj,bj,cj in [(ai+1,bi,ci),(ai,bi+1,ci),(ai,bi,ci+1)]:
        if (aj<=x-1) and (bj<=y-1) and (cj<=z-1) and (not done[aj][bj][cj]):
            hq.heappush(possibles,(a[aj]+b[bj]+c[cj],aj,bj,cj))
            done[aj][bj][cj] = 1

### FIXED CODE ###

import heapq as hq

x,y,z,k = map(int,input().split())
a = list(map(lambda x:int(x) * (-1),input().split()))
b =list(map(lambda x:int(x) * (-1),input().split()))
c = list(map(lambda x:int(x) * (-1),input().split()))
a.sort()
b.sort()
c.sort()
possibles = [(a[0]+b[0]+c[0],0,0,0)]

done = set()
done |= {(0,0,0)}
def neibor(ai,bi,ci,possibles,done):
    for aj,bj,cj in [(ai+1,bi,ci),(ai,bi+1,ci),(ai,bi,ci+1)]:
        if (aj<=x-1) and (bj<=y-1) and (cj<=z-1) and (not (aj,bj,cj) in done):
            hq.heappush(possibles,(a[aj]+b[bj]+c[cj],aj,bj,cj))
            done  |= {(aj,bj,cj)}
    

def conf(possibles,done):
    yam,ai,bi,ci = hq.heappop(possibles)
    print(-1*yam)
    neibor(ai,bi,ci,possibles,done)

for i in range(k):
    yam,ai,bi,ci = hq.heappop(possibles)
    print(-1*yam)
    for aj,bj,cj in [(ai+1,bi,ci),(ai,bi+1,ci),(ai,bi,ci+1)]:
        if (aj<=x-1) and (bj<=y-1) and (cj<=z-1) and (not (aj,bj,cj) in done):
            hq.heappush(possibles,(a[aj]+b[bj]+c[cj],aj,bj,cj))
            done  |= {(aj,bj,cj)}
### BUGGY CODE ###

A,B,C=(int(i) for i in input().split())
counter=0

while C>0:
  C-=1
  counter+=1
  if B>0:
    B-=1
    counter+=1
  elif A>0:
    A-=1
  else:
    break
    
if B>0:
  counter+=B
  
print(counter)


### FIXED CODE ###

A,B,C=(int(i) for i in input().split())
counter=0

#BとCから
if C>=B:
  counter+=B*2
  C=C-B
  B=0
  if C>A:
    counter+=A+1
  else:
    counter+=C
  
else:
  counter+=C*2
  B-=C
  C=0
  counter+=B
  
print(counter)
### BUGGY CODE ###

import re

S = str(input())
k=int(0)

while S.find('ABC')>=0:
#    S = S[:S.rfind('ABC')] + 'BCA' + S[(S.rfind('ABC')+3):]
#    k +=1
    matchedList = re.findall("ABC",S)
    k += len(matchedList)
    S = S.replace('ABC', 'BCA')

ans = (int(k))

print(ans)

### FIXED CODE ###

s = input()
ans = 0
cntA = 0
for i in range(0, len(s) - 1):
    if s[i] == 'A':
        cntA += 1
    elif s[i: i + 2] == "BC":
        ans += cntA
    elif i > 0 and s[i - 1: i + 1] == "BC":
        continue
    else:
        cntA = 0
print(ans)
### BUGGY CODE ###

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

A.sort(reverse=True)

if N == 2:
    print(A[0])
    sys.exit()

if N == 3:
    print(A[0]+A[1])
    sys.exit()

B = []
B.append(A[0])
B.append(A[1])
B.append(A[2])
ans = A[0]+A[1]

for i in range(3,N):
    tmp = min(B[0],B[len(B)-1])
    point = len(B)
    for j in range(len(B)-1):
        if tmp < min(B[j],B[j+1]):
            tmp = min(B[j],B[j+1])
            point = j
    ans += tmp
    B.insert(point+1,A[i])

print(ans)





### FIXED CODE ###

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

A.sort(reverse=True)

if N == 2:
    print(A[0])
    sys.exit()

if N == 3:
    print(A[0]+A[1])
    sys.exit()

B = []
B.append(A[1])
B.append(A[2])
B.append(A[2])
ans = A[0]+A[1]

tmp = 0

for i in range(3,N):
    ans += B[tmp]
    tmp += 1
    B.append(A[i])
    B.append(A[i])

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

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

id_set = set(range(N + 1))

for m in range(M):
  L, R = map(int, input().split())
  id_set = id_set & set(range(L, R + 1, 1))
  if len(id_set) == 0:
    break
  
print(len(set(range(1, N + 1, 1)) & id_set))

### FIXED CODE ###

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

L = list(range(M))
R = list(range(M))

for m in range(M):
  L[m], R[m] = map(int, input().split())

L_max = max(L)
R_min = min(R)

print(R_min - L_max + 1 if L_max <= R_min else 0)
### BUGGY CODE ###

h,w=map(int,input().split())
s=[input()for _ in range(h)]

yoko=[[0]*2005 for _ in range(2005)]
tate=[[0]*2005 for _ in range(2005)]

for i in range(h):
	for j in range(w):
		if s[i][j] == ".":
			yoko[i][j]+=1
			if j>0:
				yoko[i][j]+=yoko[i][j-1]
	for j in range(w-2,-1,-1):
		yoko[i][j] = max(yoko[i][j],yoko[i][j+1]) if yoko[i][j] else 0

for j in range(w):
	for i in range(h):
		if s[i][j] == ".":
			tate[i][j]+=1
			if i>0:
				tate[i][j]+=tate[i-1][j]
	for i in range(h-2,-1,-1):
		tate[i][j] = max(tate[i][j],tate[i+1][j])  if tate[i][j] else 0

ans = 0
for i in range(h):
	for j in range(w):
		ans = max(ans,yoko[i][j]+tate[i][j]-1)
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
s=[input()for _ in range(h)]

yoko=[[0]*2005 for _ in range(2005)]
tate=[[0]*2005 for _ in range(2005)]

for i in range(h):
	for j in range(w):
		if s[i][j] == ".":
			yoko[i][j]+=1
			if j>0:
				yoko[i][j]+=yoko[i][j-1]
	for j in range(w-2,-1,-1):
		yoko[i][j] = max(yoko[i][j],yoko[i][j+1]) if yoko[i][j] else 0

for j in range(w):
	for i in range(h):
		if s[i][j] == ".":
			tate[i][j]+=1
			if i>0:
				tate[i][j]+=tate[i-1][j]
	for i in range(h-2,-1,-1):
		tate[i][j] = max(tate[i][j],tate[i+1][j])  if tate[i][j] else 0

ans = 0
for i in range(h):
	for j in range(w):
		ans = max(ans,yoko[i][j]+tate[i][j]-1)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
A1 = []
A2 = []
 
for i in range(N):
    A1.append(i + A[i])
    A2.append(i - A[i])
 
count = 0
for i in A1:
    count += A2.count(i)
        
print(count)

### FIXED CODE ###

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

A1 = []
A2 = []

for i in range(N):
    A1.append(i + A[i])
    A2.append(i - A[i])

C_A1 = collections.Counter(A1)
C_A2 = collections.Counter(A2)
ans = 0
for i in range(N):
    ans += C_A1[i]*C_A2[i]
    
print (ans)
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10 ** 5)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    H, W = LI()
    S = np.ones((H, W))
    for i in range(H):
        str = input()
        for j, s in enumerate(str):
            if s == '#':
                S[i][j] = 0

    L = S.copy()
    R = S.copy()
    U = S.copy()
    D = S.copy()
    for i in range(H):
        for j in range(1, W):
            if S[i][j]:
                L[i][j] = L[i][j-1] + 1
            if S[i][W-j-1]:
                R[i][W-j-1] = R[i][W-j] + 1

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

    ans = int(np.max(L+R+U+D)) - 3
    print(ans)


main()


### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10 ** 5)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    H, W = LI()
    S = np.ones((H, W), dtype=int)
    for i in range(H):
        str = input()
        for j, s in enumerate(str):
            if s == '#':
                S[i][j] = 0

    L = S.copy()
    R = S.copy()
    U = S.copy()
    D = S.copy()
    for j in range(1, W):
        L[:, j] = (L[:, j-1] + 1)*S[:, j]
        R[:, W-j-1] = (R[:, W-j] + 1) * S[:, W-j-1]

    for i in range(1, H):
        U[i][:] = (U[i-1][:] + 1)*S[i][:]
        D[H-i-1][:] = (D[H-i][:] + 1)*S[H-i-1][:]

    ans = (L+R+U+D).max() - 3
    print(ans)


main()
### BUGGY CODE ###

def main():
    N,K,Q=map(int,input().split())
    score=[K]*N
    A=[int(input()) for _ in range(Q)]
    for i in A:
        for j in range(i-1):
            score[j]-=1
        for k in range(i,N):
            score[k]-=1
    for s in score:
        if s>0:
            print('Yes')
        else:
            print('No')

if __name__=='__main__':
    main()


### FIXED CODE ###

n, k, q = map(int, input().split())
points = [k] * n
a = []
for i in range(q):
    a.append(int(input())-1)
for cand in a:
    points[cand] += 1
points = [i-q for i in points]
ans = ["Yes" if i > 0 else "No" for i in points]
print(*ans, sep="\n")
### BUGGY CODE ###

class Sequence:
    def __init__(self,num, seq):
        self.n = num
        self.sequence = seq

def LinearSearch(A, n, key):
    i=0
    A[n] = key
    while A[i] != key:
        i += 1
    if i==n:
        return "NOT_FOUND"
    return i

if __name__ == "__main__":

    n = int(raw_input())
    x =	map(int, raw_input().split())
    x.append(" ")
    A = Sequence(n, x)
    n =	int(raw_input())
    x =	map(int, raw_input().split())
    x.append(" ")
    B = Sequence(n, x)

    C_num = 0

    for i in range(B.n):
        res = LinearSearch(A.sequence, A.n, B.sequence[i])
        if res != "NOT_FOUND":
            C_num += 1

    print(C_num)

### FIXED CODE ###

def BinarySearch(A, n, key):
    #left:left end index                                      
    #right:right end index + 1                                
    left = 0
    right = n

    while left < right:
        mid = (left+right)/2
        if A[mid] == key:
            return mid
        elif key < A[mid]:
            right = mid
        elif key > A[mid]:
            left = mid + 1

    return "NOT_FOUND"


if __name__ == "__main__":
    n1 = int(raw_input())
    x1 = map(int, raw_input().split())
    n2 = int(raw_input())
    x2 = map(int, raw_input().split())

    C_num = 0

    for i in range(n2):
	if BinarySearch(x1, n1, x2[i]) != "NOT_FOUND":
            C_num += 1

    print(C_num)
### BUGGY CODE ###

n=int(input())
lamp = [int(input()) for i in range(n)]
lst = []
cnt = 0
select = lamp[0]
while True:
  if select in lst or cnt == n:
    print(-1)
    break;
  elif select == 2:
    cnt += 1
    print(cnt)
    break;
  else:
    lst.append(select)
    select = lamp[select-1]
    cnt += 1

### FIXED CODE ###

n=int(input())
lamp = [int(input()) for i in range(n)]
cnt = 0
select = lamp[0]
while True:
  if cnt>n:
    print(-1)
    break;
  elif select == 2:
    cnt += 1
    print(cnt)
    break;
  else:
    select = lamp[select-1]
    cnt += 1