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

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
a = [LI() for _ in range(N)]
dp = [[0] * (2**N) for _ in range(N)]

q = [set() for _ in range(N)]
b = 1
for i in range(N):
    if a[0][i]:
        dp[0][b] = 1
        q[0].add(b)
    b <<= 1


for i in range(1,N):
    for k in q[i-1]:
        v = dp[i-1][k]
        b = 1
        for l in a[i]:
            if l and k & b == 0:
                m = k | b
                dp[i][m] = (dp[i][m] + v) % MOD
                q[i].add(m)
            b <<= 1

ans = dp[-1][2**N-1] % MOD
print(ans)

### FIXED CODE ###

import sys

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    N = NI()
    a = [LI() for _ in range(N)]
    dp = [[0] * (2**N) for _ in range(N)]

    q = [[] for _ in range(N)]
    b = 1
    for i in range(N):
        if a[0][i]:
            dp[0][b] = 1
            q[0].append(b)
        b <<= 1

    for i in range(1,N):
        for k in q[i-1]:
            v = dp[i-1][k]
            b = 1
            for l in a[i]:
                if l and k & b == 0:
                    m = k | b
                    if dp[i][m] == 0: q[i].append(m)
                    dp[i][m] = (dp[i][m] + v) % MOD
                b <<= 1

    print(dp[-1][2**N-1])

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

n=int(input())
for i in range(1,n+1):
    count=0
    for x in range(1,i):
        for y in range(1,i-x):
            for z in range(1,i-x-y):
                if x*x+y*y+z*z+x*y+y*z+z*x==i:
                    count+=1
    print(count)


### FIXED CODE ###

n=int(input())
l=[0]*10**7
s=int(n**0.7)+10
for x in range(1,s):
    for y in range(1,s-x):
        for z in range(1,s-x-y):
            l[x*x+y*y+z*z+x*y+y*z+z*x-1]+=1
for i in range(n):
    print(l[i])
### BUGGY CODE ###

import bisect
n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
a.sort()

while(m):
  m-=1
  now=a.pop()
  ind=bisect.bisect_left(a,(now//2))
  a.insert(ind,(now//2))

print(sum(a))

### FIXED CODE ###

import heapq as hp
n,m=[int(x) for x in input().rstrip().split()]
a=[-int(x) for x in input().rstrip().split()]

hp.heapify(a)
a.sort()

while(m):
  
  m-=1
  now=hp.heappop(a)
  now=-((-now)//2)
  hp.heappush(a,now)
  
print(-sum(a))
### BUGGY CODE ###

N, M = map(int, input().split())
AS = list(map(int, input().split()))
for i in range(M):
    hi = max(range(N), key = lambda n : AS[n])
    AS[hi]//=2
print(sum(AS))


### FIXED CODE ###

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

import math

buckets = [[] for i in range(31)]
count = [0 for i in range(31)]
for num in AS:
    buckets[math.floor(math.log(num)/math.log(2))].append(num)
    
for lst in buckets: lst.sort(reverse=True)

hi = 30
while buckets[hi-1] == []: hi -= 1
found = 0
while True:
    try:
        if M > found:
            for i in range(hi, 31):
                count[i] += 1
            hi -= 1
            M -= found
            found += len(buckets[hi])
        else:
            total = 0
            for i in range(hi):
                total += sum(buckets[i])
                
            lst = []
            for i in range(hi, 30):
                for item in buckets[i]:
                    lst.append(item // pow(2, count[i]))
             
            lst.sort(reverse=True)
            
            for i in range(M):
                lst[i] //= 2

            total += sum(lst)

            print(total)
            break
    except:
        print(0)
        break
### BUGGY CODE ###

n = int(input())
a = [i for i in range(1, n + 1)]
print(sum(a) - n)

### FIXED CODE ###

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

A, B = map(int, input().split())

for i in range(10**9):
  k = abs(A - i)
  l = abs(B - i)
  if k == l:
    print(k)
  else:
    print('IMPOSSIBLE')

### FIXED CODE ###

A, B = map(int, input().split())
 
if (A + B)%2 == 0:
  k = (A + B)/2
  print(round(k))
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
dp = []
for i in range(N):
  L = [0]*(K+1)
  dp.append(L)
for i in range(A[0]+1):
  dp[0][i] = 1
for i in range(1,N):
  cur = [0]*(K+2)
  for j in range(K+1):
    cur[j+1] = cur[j]+dp[i-1][j]
  for k in range(K+1):
    if k > A[i]:
      dp[i][k] = cur[k+1]-cur[k-A[i]]
    else:
      dp[i][k] = cur[k+1]
print(dp[N-1][K]%(10**9+7))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
dp = []
for i in range(N):
  L = [0]*(K+1)
  dp.append(L)
for i in range(A[0]+1):
  dp[0][i] = 1
for i in range(1,N):
  cur = [0]*(K+2)
  for j in range(K+1):
    cur[j+1] = (cur[j]+dp[i-1][j])%(10**9+7)
  for k in range(K+1):
    if k > A[i]:
      dp[i][k] = cur[k+1]-cur[k-A[i]]
    else:
      dp[i][k] = cur[k+1]
print(dp[N-1][K]%(10**9+7))
### BUGGY CODE ###

m = int(input())
for i in range(1,int(m**0.5)+1):
    if m % i == 0 and m//i <= 10**9:
        print("0 0 " + str(m//i) +" 0 0 " + str(i))
        exit()

### FIXED CODE ###

s = int(input())
x = s % 10**9
y = s // 10**9
if x > 0:
    x -= 10**9
    y += 1
print(0,0,10**9,1,-x,y)
### BUGGY CODE ###

class UnionFind():
    def __init__(self,size):
        self.table = [[-1,1] for _  in range(size)] # root, count
    def find(self,x):
        while self.table[x][0] >= 0:
            x = self.table[x][0]
        root = x
        while self.table[x][0] >= 0:
            x = self.table[x][0]
            self.table[x][0] = root
        return root
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1][0] != self.table[s2][0]:
                if self.table[s1][0] < self.table[s2][0]:
                    self.table[s2][0] = s1
                    self.table[s1][1] += self.table[s2][1]
                else:
                    self.table[s1][0] = s2
                    self.table[s2][1] += self.table[s1][1]
            else:
                self.table[s1][0] += -1
                self.table[s2][0] = s1
                self.table[s1][1] += self.table[s2][1]
        return


N, M = map(long, raw_input().split())
uf = UnionFind(N)
V = [map(long, raw_input().split()) for _ in range(M)]

answers = []
for v in reversed(V):
  ans = 0
  tree_sizes = []
  for t in uf.table:
    if t[0] < 0:
      tree_sizes.append(t[1])
  for i in range(len(tree_sizes)):
    for j in range(i+1, len(tree_sizes)):
      ans += tree_sizes[i]*tree_sizes[j]
  answers.append(ans)
  uf.union(v[0]-1, v[1]-1)
for a in reversed(answers):
  print a



### FIXED CODE ###

class UnionFind():
    def __init__(self,size):
        self.table = [[-1,1] for _  in range(size)] # root, count
    def find(self,x):
        while self.table[x][0] >= 0:
            x = self.table[x][0]
        return x
    def union(self,x,y):
        szsz = 0
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            szsz = self.table[s1][1]*self.table[s2][1]
            if self.table[s1][0] != self.table[s2][0]:
                if self.table[s1][0] < self.table[s2][0]:
                    self.table[s2][0] = s1
                    self.table[s1][1] += self.table[s2][1]
                else:
                    self.table[s1][0] = s2
                    self.table[s2][1] += self.table[s1][1]
            else:
                self.table[s1][0] += -1
                self.table[s2][0] = s1
                self.table[s1][1] += self.table[s2][1]
        return szsz


N, M = map(long, raw_input().split())
uf = UnionFind(N)
V = [map(long, raw_input().split()) for _ in range(M)]

ans = N*(N-1)/2
answers = []
for v in reversed(V):
  answers.append(ans)
  szsz = uf.union(v[0]-1, v[1]-1)
  ans -= szsz
for a in reversed(answers):
  print a
### BUGGY CODE ###

s = input()
K = int(input())
def substring(S):
    N = len(S)
    ls = []
    for i in range(1,N+1):
        for j in range(0,N-i+1):
            ls.append(S[j:j+i])
    setls = set(ls)
    ls = list(setls)
    ls.sort()
    return ls
print(substring(s)[K-1])

### FIXED CODE ###

s = input()
K = int(input())

def substring(S):
    N = len(S)
    ls = []
    for i in range(1,min(6,N+1)):
        for j in range(0,N-i+1):
            ls.append(S[j:j+i])
    setls = set(ls)
    ls = list(setls)
    ls.sort()
    return ls
print(substring(s)[K-1])
### BUGGY CODE ###

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

lp = [0]
lx = [0]

nowlp = 0
nowlx = 0

for x in range( len(a) ):
  nowlp += a[x]
  nowlx ^= a[x]

  lp.append(nowlp)
  lx.append(nowlx)
#print lp
#print lx

ans = 0

for l in range(1,len(a)+1 ):
  for r in range(l,len(a)+1 ):
    if lp[r] - lp[l-1] == lx[r] ^ lx[l-1]:
      #print l,r,lp[r],lp[l], lx[r] ,lx[l]
      ans += 1

print ans


### FIXED CODE ###

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

lp = [0]
nowlp = 0

for x in range( len(a) ):
  nowlp += a[x]
  lp.append(nowlp)

ans = 0
prev = [ [0,0] ]

for l in range(0,n-1):
  r = prev[l][1] + 1
  ans += prev[l][1]-l
  now = lp[r] - lp[l]

  while r <= n-1 and now^a[r] == now+a[r]:
    ans += 1
    now += a[r]
    r += 1
  prev.append( [l,r-1] )

ans += n
print ans
### BUGGY CODE ###

import  itertools
n,m,q=map(int,input().split())

t=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    a-=1
    b-=1
    t.append([a,b,c,d])

def judge(l):
    cv=[1 for h in range(n)]
    for i in range(q):
        if l[i]==1:
            cv[t[i][1]]=cv[t[i][0]]+t[i][2]
    for i in range(n):
        if cv[i]>m:
            return False
    for i in range(q):
        if l[i]==1:
            if cv[t[i][1]]-cv[t[i][0]]!=t[i][2]:
                return False
    return True

num=[0,1]
ans=0

for df in itertools.product(num,repeat=q):
    ty=list(df)
    if judge(ty):
        to=0

        for i in range(q):
            if ty[i]==1:
                to+=t[i][3]
        ans=max(ans,to)

print(ans)





### FIXED CODE ###

import  itertools
n,m,q=map(int,input().split())

t=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    a-=1
    b-=1
    t.append([a,b,c,d])

def judge(l):
    ans=0
    for i in range(q):
        a,b,c,d=t[i]
        if l[b]-l[a]==c:
            ans+=d
    return ans

num=[]
ans=0
for i in range(1,m+1):
    num.append(i)

for df in itertools.combinations_with_replacement(num,n):

    ty=list(df)
    f=judge(ty)
    ans=max(ans,f)

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

n = int(input())
a = input().split(" ")

sum = 1
for i in a:
  sum = sum * int(i)

if sum > 1000000000000000000:
  print(-1)
else:
  print(sum)

### FIXED CODE ###

n = int(input())
a = input().split(" ")

sum = 1
for i in a:
  sum = sum * int(i)
  if sum > 1000000000000000000:
    break

if "0" in a:
  print(0)
elif sum > 1000000000000000000:
  print(-1)
else:
  print(sum)
### BUGGY CODE ###

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None

if D.count(0)==1 and D[0]==0:

    mul=1
    n=1

    for i in range(1,max(D)+1):
        m=D.count(i)
        mul=mul*n**m
        n=m
    
    ans=mul%998244353

else:
    ans=0

print(int(ans))

### FIXED CODE ###

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None


if D.count(0)==1 and D[0]==0:

    L=[0]*(max(D)+1)

    for i in range(len(D)):
        L[D[i]]+=1

    mul=1

    for i in range(len(L)-1):
        mul*=L[i]**L[i+1]%998244353
    
    ans=mul%998244353

else:
    ans=0

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

import sys
from bisect import insort_left
input = sys.stdin.readline
 
def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    for _ in range(m):
        b = a.pop()//2
        insort_left(a, b)
    print(sum(a))
 
 
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

import numpy as np

def main():
    n, m = map(int, input().split())
    a = np.array([int(i) for i in input().split()])
    a.sort()

    while True:
        temp = a[-1]//2
        a[-1] //= 2
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
            break
        elif n - ind < m:
            a[ind:] = a[ind:]//2
            a.sort()
            m = m - (n-ind)
        else:
            a[-m:] = a[-m:]//2
            print(np.sum(a))
            break

main()
### BUGGY CODE ###

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

ans = 1

for i in range(N):
    ans *= A[i]

    if ans > 1000000000000000000:
        ans = -1

print(ans)


### FIXED CODE ###

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

ans = 1

if 0 in A:
    print(0)
    exit()

for i in range(N):
    ans *= A[i]

    if ans > 10**18:
        ans = -1
        break

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

n, m = map(int,input().split())
a = list(map(int,input().split()))
for y in range(m):
    b, c = map(int,input().split())
    for i in range(b):
        if c <= min(a):
            break
        ai = a.index(min(a))
        a[ai] = c
        
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(reverse=True, key=lambda x:x[1])
tmp = []
for B, C in bc:
    tmp += [C]*B
    if len(tmp) >= n:
        break

a.extend(tmp)
a.sort(reverse=True)

print(sum(a[:n]))
### BUGGY CODE ###

from collections import defaultdict
import sys
import math

input = sys.stdin.readline

# 素因数分解O(√n)


def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    pairs = True
    setp = True
    for i in range(N):
        pf = primeFactor(A[i])
        for k in pf.keys():
            primes[k] += 1
            if primes[k] != 1:
                pairs = False
            if primes[k] == N:
                setp = False
    if pairs:
        print('pairwise coprime')
    elif setp:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
from collections import defaultdict
import sys
import math

input = sys.stdin.readline

# 素因数分解O(√n)


def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    setp = True
    pairs = True
    if gcd(*A) != 1:
        setp = False
        pairs = False
    else:
        for i in range(N):
            pf = primeFactor(A[i])
            for k in pf.keys():
                primes[k] += 1
                if primes[k] != 1:
                    pairs = False
            if not pairs:
                break
    if pairs:
        print('pairwise coprime')
    elif setp:
        print('setwise coprime')
    else:
        print('not coprime')


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

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])
### BUGGY CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
cnt = l[k-1]
p = 1
g = k-1
i = 0
while(i < k-1):
    cnt = cnt*l[g-1]
    g = g-1
    i = i+1

g = g+1
pr = l[g-1]
while(k < n):
    cur = cnt*l[k]
    cur = cur//pr
    g = g+1
    pr = l[g-1]
    if cur > cnt:
        print("Yes")

    else:
        print("No")

    cnt = cur
    k = k+1


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
l = list(map(int,input().split()))
#print(l)
cnt = l[k-1]
p = 1
g = 0
g = g+1
pr = l[g-1]
while(k < n):
    if l[k] > pr:
        sys.stdout.write("Yes")
        print("")

    else:
        sys.stdout.write("No")
        print("")

    g = g+1
    pr = l[g-1]
    k = k+1
### BUGGY CODE ###

N = int(input())
DP = [100000000] * (N+1)
DP[0] = 0
for i in range (N):
    DP[i + 1] = DP[i] + 1
    for j in range (100):
        if 6**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 6**j] + 1)
    for j in range (100):
        if 9**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 9**j] + 1)
print(DP[N])

### FIXED CODE ###

N = int(input())
DP = [100000000] * (N+1)
DP[0] = 0
for i in range (N):
    DP[i + 1] = DP[i] + 1
    for j in range (8):
        if 6**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 6**j] + 1)
    for j in range (8):
        if 9**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 9**j] + 1)
print(DP[N])
### BUGGY CODE ###

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

aa = dict.fromkeys(a)
f = 0
cnt = 0
for i in aa:
  if i == 0:
    if a.count(0) == 1:
      continue
    else:
      f = 1
  else:
    if a.count(i) == 2:
      cnt += 1
    else:
      f = 1
if f == 0:
  print(pow(2, cnt))
else:
  print(0)

### FIXED CODE ###

mod = 1000000007

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

data = [0]*N
for i in a:
  data[i] += 1

cnt = 0
for i in range(1,len(data)):
  if data[i] == 2:
    cnt += 1
  elif data[i] == 0:
    continue
  else:
      print(0)
      exit()
print(pow(2, cnt) %mod)
### BUGGY CODE ###

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

D = []

for _ in range(K):
    L, R = map(int, input().split())

    for i in range(L, R+1):
        D.append(i)

dp = [0] * 300000
dp[1] = 1

for i in range(2, N+1):
    for d in D:
        if i - d < 1:continue
        dp[i] += dp[i-d]
        dp[i] %= 998244353

print(dp[N])

### FIXED CODE ###

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

L, R = [], []

for _ in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * 300000
dpsum = [0] * 300000
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for j in range(K):
        li = min(L[j], i)
        ri = min(R[j], i + 1)
        dp[i] += dpsum[i - li] - dpsum[i - ri - 1]

    dp[i] %= 998244353
    dpsum[i] = dpsum[i-1] + dp[i]

print(dp[N])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
dis_list = []
for i in range(Q):
    s = list(map(int, input().split()))
    dis_list.append(s)
for j in range(len(dis_list)):
    for k in range(len(A)):
        if A[k] == dis_list[j][0]:
            A[k] = dis_list[j][1]
    print(sum(A))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
count = Counter(A) #not dict!!
temp_sum = sum(A)
for _ in range(Q):
    before, after = map(int, input().split())
    temp_sum += (after - before) * count[before]
    count[after] += count[before]
    count[before] = 0
    print(temp_sum)
### BUGGY CODE ###

S = input()
N = len(S)

ans = [0] * N

for i in range(N):
  # 初期位置と異なる文字
  if S[i] == 'R':
    u = i+1
    while S[u] == S[i]:
      u += 1
    if (u-i) % 2 == 0:
      ans[u] += 1
    else:
      ans[u-1] += 1
  else:
    u = i-1
    while S[u] == S[i]:
      u -= 1
    if (i-u) % 2 == 0:
      ans[u] += 1
    else:
      ans[u+1] += 1
print(*ans)

### FIXED CODE ###

S = input()
N = len(S)
ans = [0] * N
i = 0
while i < N:
  if i == N-1:# 一番右はL固定
    ans[N-1] +=1
    break
  count = 1
  while S[i+count] == S[i]:
    count += 1
    if count == N-i:
      break
  if S[i] == 'R':
    ans[i+count-1] += (count+1)//2
    ans[i+count] += count//2
  else:
    ans[i] += (count+1)//2
    ans[i-1] += count//2
  i += count
print(*ans)
### BUGGY CODE ###

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [(i+a[i]) for i in range(n)]
    R = [(i-a[i]) for i in range(n)]
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    for i,Li in enumerate(L):
        count += len([idx for idx,x in enumerate(R[(i+1):n]) if x==Li])

    print(count)

main()


### FIXED CODE ###

from collections import Counter

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [0]*n
    R = [0]*n
    for i,ai in enumerate(a):
        L[i] = i+ai
        R[i] = i-ai
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    c = Counter(R)
    for Li in L:
        count += c.get(Li,0)

    print(count)

main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(1,n+1):
    b.append(a.index(i)+1)
    
print(*b)

### FIXED CODE ###

import numpy 
n = int(input())
a = list(map(int,input().split()))

print(*numpy.argsort(a)+1)
### BUGGY CODE ###

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

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

import sys
INT_MAX = sys.maxsize

import itertools
ans = INT_MAX
for sub_dots in itertools.combinations(dots, K):
    #print(sub_dots)
    sub_x = [x for x,y in sub_dots]
    sub_y = [y for x,y in sub_dots]
    min_x = min(sub_x)
    min_y = min(sub_y)
    max_x = max(sub_x)
    max_y = max(sub_y)
    area = (max_x-min_x) * (max_y-min_y)
    ans = min(ans, area)
print(ans)

### FIXED CODE ###

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    a[i] = [a[i],i]
l1 = 0
r1 = n-1
l2 = l1
r2 = r1
a.sort(reverse=1)
dp = [[0]*(n+1) for i in range(n+1)]
ans = 0
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + a[i-1][0] * abs(a[i-1][1]-i+1)
    dp[0][i] = dp[0][i-1] + a[i-1][0] * abs(n-(a[i-1][1])-i)
    for j in range(1,i):
        dp[j][i-j] = max(dp[j-1][i-j]+a[i-1][0]*abs(a[i-1][1]-j+1),dp[j][i-j-1]+a[i-1][0]*abs(n-(a[i-1][1])-(i-j)))
for i in dp:
    ans = max(ans,max(i))
print(ans)

### FIXED CODE ###

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

for i in range(n):
    a[i] = [a[i],i]
l1 = 0
r1 = n-1
l2 = l1
r2 = r1
a.sort(reverse=1)
dp = [[0]*(n+1) for i in range(n+1)]
ans = 0
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + a[i-1][0] * abs(a[i-1][1]-i+1)
    dp[0][i] = dp[0][i-1] + a[i-1][0] * abs(n-(a[i-1][1])-i)
    for j in range(1,i):
        dp[j][i-j] = max(dp[j-1][i-j]+a[i-1][0]*abs(a[i-1][1]-j+1),dp[j][i-j-1]+a[i-1][0]*abs(n-(a[i-1][1])-(i-j)))
for i in dp:
    ans = max(ans,max(i))
print(ans)