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

k = int(input())
memo = {}

def gcd(x,y):

    while y:
        x,y = y,x%y

    return x

total = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            total += gcd(gcd(a,b),c)

print(total)


### FIXED CODE ###

from math import gcd
k=int(input())
        
r=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            r+=gcd(gcd(i,j),l)
print(r)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    
    SUM = []
    for i in range(N):
        SUM.append(sum(A[i:])%(10**9+7))
    
    ans = 0
    for i in range(N-1):
        ans += A[i]*SUM[i+1]
        ans = ans%(10**9+7)
    
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    
    SUM = [sum(A)]
    for i in range(1,N):
        SUM.append((SUM[i-1]-A[i-1])%(10**9+7))
    
    ans = 0
    for i in range(N-1):
        ans += A[i]*SUM[i+1]
        ans = ans%(10**9+7)
    
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

a = input()
b = input()
c = input()


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = {i: True for i in range(-9000, 9001)}
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if not comp(si, tj):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ac[c_idx] and check_bc[c_idx - b_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)


### FIXED CODE ###

a = input()
b = input()
c = input()

OFFSETS = 9000


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = [True] * (OFFSETS * 2 + 10)
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if not comp(si, tj):
                check_st[i - j + OFFSETS] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx + OFFSETS] and check_ac[
                c_idx + OFFSETS] and check_bc[c_idx - b_idx + OFFSETS]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

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

from collections import deque

s = deque(list(map(str, input().rstrip())))
q = int(input())

for _ in range(q):
    li = list(map(str, input().split()))
    if li[0] == "1":
        s.reverse()
    elif li[1] == "1":
        s.appendleft(li[2])
    else:
        s.append(li[2])

print("".join(s))

### FIXED CODE ###

from collections import deque

s = deque(list(map(str, input().rstrip())))
q = int(input())

state = 1
for _ in range(q):
    li = list(map(str, input().split()))
    if li[0] == "1":
        state *= -1
    elif (li[1] == "1" and state == 1) or (li[1] == "2" and state == -1):
        s.appendleft(li[2])
    else:
        s.append(li[2])

if state == -1:
    s.reverse()

print("".join(s))
### BUGGY CODE ###

MOD = 10**9+7

def extgcd(a,b): #互いに素なa,bについて、a*x+b*y=1の一つの解
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,mod): # (x/a)%MODをしたい時は x%MOD * mod_inv(a,MOD)%MOD
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def lcm(a, b):
    return a*b//gcd(a,b)

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

lcm_ = a[0]
ans = 1
for i in range(1,n):
    if lcm_%MOD * mod_inv(a[i],MOD)%MOD != 0:
        lcm_new = lcm(lcm_, a[i])
        ans = ans*(lcm_new%MOD *mod_inv(lcm_,MOD)%MOD)
        lcm_ = lcm_new
    ans += lcm_%MOD * mod_inv(a[i], MOD)%MOD

print(ans%MOD)






### FIXED CODE ###

MOD = 10**9+7
import fractions

def extgcd(a,b): #互いに素なa,bについて、a*x+b*y=1の一つの解
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,mod): # (x/a)%MODをしたい時は x%MOD * mod_inv(a,MOD)%MOD
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod


# def gcd(a, b):
#     if b == 0:
#         return a
#     return gcd(b, a%b)

# def lcm(a, b):
#     return a*b//gcd(a,b)

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

lcm_ = a[0]
for i in range(1, n):
    lcm_ = lcm_ * a[i] // fractions.gcd(lcm_, a[i])

# lcm_ = a[0]
ans = 0
for i in range(0,n):
    # if lcm_ % a[i] != 0:
    #     lcm_new = lcm(lcm_, a[i])
    #     ans = ans*(lcm_new%MOD *mod_inv(lcm_,MOD)%MOD)
    #     lcm_ = lcm_new

    ans += lcm_%MOD * mod_inv(a[i], MOD)%MOD

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

from math import sqrt
import heapq

class Dijkstra(object):
    def __init__(self, n):
        self.visited = {}
        self.edges = [{} for i in range(n)]
        self.cnt = 0
        self.n = n

    def add_edge(self, s, t, w, directed=True):
        self.edges[s][t] = w
        if not directed:
            self.edges[t][s] = w

    def solve(self, start):
        que = []
        heapq.heappush(que, (0,start, start))

        while que:
            if self.cnt == self.n:
                break
            w, s, prev = heapq.heappop(que)
            if s in self.visited:continue
            self.visited[s] = w
            self.cnt += 1
            for edge in self.edges[s]:
                if edge not in self.visited:
                    heapq.heappush(que, (w+self.edges[s][edge], edge, s))
        return self.visited

def calc_dist(p1,p2):
    return max(0, sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) - (p1[2]+p2[2]))

xs, ys, xg, yg = map(int, input().split())
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
p = [[xs,ys,0], [xg,yg,0]] + p
n += 2

D = Dijkstra(n)
for i in range(n):
    for j in range(i,n):
        D.add_edge(i,j, calc_dist(p[i],p[j]), directed=False)
ans = D.solve(0)[1]
print(ans)

### FIXED CODE ###

from math import sqrt
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
# https://atcoder.jp/users/nadare881

def calc_dist(p1,p2):
    return max(0, sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) - (p1[2]+p2[2]))

xs, ys, xg, yg = map(int, input().split())
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
p = [[xs,ys,0], [xg,yg,0]] + p
n += 2
edges = [[float("inf")]*n for i in range(n)]
for i in range(n):
    for j in range(i,n):
        if i == j :continue
        edges[i][j] = edges[j][i] = calc_dist(p[i], p[j])
edges = csgraph_from_dense(edges, null_value=float("inf"))
dist = dijkstra(edges, directed=False, indices=0)
print(dist[1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[0]*N
for j in range(N):
    B[j]=A[j]-j-1
max=B[0]
min=B[0]
for k in range(len(B)):
  if max<=B[k]:
    max=B[k]
bt=max
for k in range(len(B)):
  if min>=B[k]:
    min=B[k]
bh=min
def sad(A,b):
  s=[0]*(len(A))
  for m in range(len(A)):
    s[m]=abs(A[m]-(b+m+1))
  return s
def sum(A):
  sum=0
  for n in range(len(A)):
    sum=sum+A[n]
  return sum
l=[]
for o in range(bh-5,bt+5):
  l.append(sum(sad(A,o)))
def quick_sort(a):
    if len(a) <= 1:
        return a
    else:
        b = []
        c = []
        for i in range(1, len(a)):
            if a[i] < a[0]:
                b.append(a[i])
            else:
                c.append(a[i])
        return quick_sort(b)+[a[0]]+quick_sort(c)
print(quick_sort(l)[0])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  B.append(A[i]-i-1)
B.sort()
if N%2==0:
  b=(B[N//2]+B[N//2-1])//2
else:
  b=B[N//2]
sad=0
for j in range(N):
  sad=sad+abs(B[j]-b)
print(sad)
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())
lis = []
for i in s:
    if i in lis:
        continue
    else:
        lis.append(i)

print(len(lis))

### FIXED CODE ###

n = int(input())
s = {}
for _ in range(n):
    s[input()] = 1

print(len(s))
### BUGGY CODE ###

from collections import deque
from itertools import combinations

def main():
    n, x, y = [int(e) for e in input().split()]

    D = dict()
    D[1] = {2}
    D[n] = {n - 1}
    for i in range(2, n):
        D[i] = {i - 1, i + 1}

    D[x].add(y)
    D[y].add(x)

    A = [0]*(n - 1)
    for c in combinations(range(1, n + 1), 2):
        Q = deque()
        Q.extend(D[c[0]])
        cnt = 0
        end = False
        while not end:
            cnt += 1
            Qex = set()
            while len(Q) != 0:
                e = Q.popleft()
                if e == c[1]:
                    Q.clear()
                    end = True
                    break

                Qex |= D[e]

            Q.extend(Qex)

        A[cnt - 1] += 1

    for a in A:
        print(a)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from itertools import combinations

def main():
    n, x, y = [int(e) for e in input().split()]

    A = [0]*(n - 1)
    for c in combinations(range(1, n + 1), 2):
        cnt = min(abs(c[1] - c[0]), abs(c[1] - y) + abs(c[0] - x) + 1, abs(c[1] - x) + abs(c[0] - y) + 1)
        A[cnt - 1] += 1

    for a in A:
        print(a)

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

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    bin_list = [[0, 0] for _ in range(60)]

    for j in range(60):
        for i in range(n):
            a[i], b = divmod(a[i], 2)
            bin_list[j][b] += 1

    sum_ = 0
    for j in range(60):
        sum_ += bin_list[j][0] * bin_list[j][1] * (2 ** j) % mod
        sum_ %= mod

    print(sum_)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    ret = 0
    magni = 1
    for j in range(60):
        bin_cnt = [0, 0]
        for i in range(n):
            a[i], b = divmod(a[i], 2)
            bin_cnt[b] += 1
        x, y = bin_cnt
        ret += x * y * magni % mod
        magni = magni * 2 % mod

    ret %= mod

    print(ret)


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

N = int(input())
A = list(map(int,input().split()))
ans = 1
for a in A:
    ans *= a
    if a == 0:
        print(0)
        exit()
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
zero = A.count(0)
one = A.count(1)

if zero >= 1:
    print(0)
elif (N - one) > 100:
    print(-1)
else:
    ans = 1
    for a in A:
        ans *= a
    if ans > 10**18:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

nums = [int(e) for e in input().split()]
x=nums[0]
y=nums[1]
Min = x
t=True
while t:
  a = Min-y
  if(abs(a)<Min):
    Min = abs(a)
  elif(abs(Min - y) > Min):
    break
print(Min)

### FIXED CODE ###

nums = [int(e) for e in input().split()]
Min=nums[0]
y=nums[1]
ans = Min % y
t = True
if (ans <= Min):
    Min = ans
    while t:
        a = abs(Min - y)
        if(a<Min):
            Min = a
        elif(a>Min):
            break
    print(Min)
else:
    print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
ans=0
for i in range(1,(m//n)+1):
    if m%i==0:
        ans=i
        
print(ans)

### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    divisors.reverse()
    return divisors

l=make_divisors(m)

for i in l:
    if i*n<=m:
        print(i)
        import sys
        sys.exit()
### BUGGY CODE ###

N = int(input())
P = list(map(float, input().split()))
P = [0] + P
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
    dp[i][0] = dp[i-1][0] * (1 - P[i])

for i in range(1, N+1):
    for j in range(1, i+1):
        dp[i][j] += dp[i-1][j-1] * P[i] + dp[i-1][j] * (1 - P[i]) 

ans = 0
if N % 2 == 0:
    start = N // 2
else:
    start = N // 2 + 1

for i in range(start, N+1):
    ans += dp[N][i]
    
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(float, input().split()))
P = [0] + P
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
    dp[i][0] = dp[i-1][0] * (1 - P[i])

for i in range(1, N+1):
    for j in range(1, i+1):
        dp[i][j] += dp[i-1][j-1] * P[i] + dp[i-1][j] * (1 - P[i]) 

ans = 0
if N % 2 == 0:
    start = N // 2
else:
    start = N // 2 + 1

for i in range(start, N+1):
    ans += dp[N][i]
    
print(ans)
### BUGGY CODE ###

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

a = set(A)
for i in a:
    dic[i] = A.count(i)

for i in range(Q):
    b, c = list(map(int, input().split()))
    if b in dic:
        if c in dic:    
            dic[c] += dic.pop(b)
        else:
            dic[c] = dic.pop(b)
    ans = 0
    for num in dic:
        ans += num * dic[num]
    print(ans)

### FIXED CODE ###

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

for i in A:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

ans = 0
for num in dic:
    ans += num * dic[num]

for i in range(Q):
    b, c = list(map(int, input().split()))
    x = 0
    if b in dic:
        x = dic.pop(b)
        if c in dic:    
            dic[c] += x
        else:
            dic[c] = x
    ans += x * (c-b)
    print(ans)
### BUGGY CODE ###

N = int(input())
items = []
ans = 0
for _ in range(N):
  item = input()
  if not item in items:
    items += item,
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
items = {}
ans = 0
for _ in range(N):
    items[input()] = None
print(len(items))
### BUGGY CODE ###

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0

q = [[0,0]]

#print (d)

while len(q) > 0:

    np = heapq.heappop(q)
    now = np[1]

    for i in range(N+2):
        if ans[i] > ans[now] + d[now][i]:
            ans[i] = ans[now] + d[now][i]
            heapq.heappush(q,[ans[i] , i])

#print (ans)
print (ans[-1])
    


### FIXED CODE ###

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0
used = [False] * (N+2)

while True:

    v = -1

    #未到達の点に関して最も数値の小さい点を選ぶ
    for i in range(N+2):
        if not used[i] and (v == -1 or ans[v] > ans[i]):
            v = i
    
    if v == -1:
        break
    
    used[v] = True
    for i in range(N+2):
        ans[i] = min(ans[i] , ans[v] + d[v][i])

#print (used,ans)
print (ans[-1])
### BUGGY CODE ###

from collections import deque
import numpy as np
 
def chk_route(c):
    global H,W,T
    ans=[]
    if c[0] != H-1:
        if T[c[0]+1][c[1]]==0:
            ans+=[c[0]+1,c[1]]
    if c[0] != 0:
        if T[c[0]-1][c[1]]==0:
            ans+=[c[0]-1,c[1]] 
    if c[1] != W-1:
        if T[c[0]][c[1]+1]==0:
            ans+=[c[0],c[1]+1]
 
    if c[1] != 0:
        if T[c[0]][c[1]-1]==0:
            ans+=[c[0],c[1]-1]

    return ans
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c+=[i,j]
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        T[c[0]][c[1]]=s
                        c += (chk_route([c.popleft(),c.popleft()]))
                
        #print(T)
        d = max(d,s)
        T=B.copy()
        
print(d-2)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
### BUGGY CODE ###

import math
n=int(input())
ans=0
while n>0:
  ans+=(n%10)
  n//=10
if ans%9==0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

import math
n=input()
ans=0
for item in n:
  ans+=int(item)
if ans%9==0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

N = int(input())
S =  input()
dp = [0] * N
min_selct = N//2
max_length = 0
for i in range(N):
    for j in range((N -i)//2): 
        if S[i+j+1:N].find(S[i:i+j+1]) >= 0:
            max_length = max(max_length,j+1)
print(max_length)

### FIXED CODE ###

n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))
### BUGGY CODE ###

s=input()
q=int(input())
queri=[]
rv=0

for i in range(q):
    tmp=list(map(lambda x: x,input().split()))
    queri.append(tmp)
    if tmp[0]=="1": rv+=1
rv=rv%2

if rv==1: s=s[::-1]
forward=""
back=""
for i in range(q):
    if queri[i][0]=="2":
        rvt=(rv+int(queri[i][1]))%2
        if rvt==1: forward+=queri[i][2]
        else: back+=queri[i][2]

    else: rv=(rv+1)%2

print(forward[::-1],end="")
print(s,end="")
print(back)

### FIXED CODE ###

s=input()
q=int(input())
queri=[]
rv=0
forward=[]
back=[]
for i in range(q):
    queri=list(map(lambda x:x,input().split()))
    if queri[0]=="2":
        rvt=(rv+int(queri[1]))%2
        if rvt==1: forward.append(queri[2])
        else: back.append(queri[2])

    else: rv=(rv+1)%2

if rv==0:
    for i in range(len(forward)-1,-1,-1):
        print(forward[i],end="")
    print(s,end="")
    for i in range(len(back)):
        print(back[i],end="")
        
if rv==1:
    for i in range(len(back)-1,-1,-1):
        print(back[i],end="")
    print(s[::-1],end="")
    for i in range(len(forward)):
        print(forward[i],end="")
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L_i=[i+1 for i in range(len(L))]

cnt=0
for i in range(N):
    P_L= [m+L[i] for m in L[i:]]
    P_L_i = [x - y for (x, y) in zip(L_i[i:],[L_i[i]] * len(L_i[i:]))]
    cnt = cnt + sum([w==z for (w, z) in zip(P_L,P_L_i)])
    
print(cnt)

### FIXED CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    L_memo = [0]*N
    cnt=0
    for i, j in enumerate(L):
        if i+j<N:
            L_memo[i+j]+=1
        if i-j>0:
            cnt+=L_memo[i-j]        
    print(cnt)
main()
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

@lru_cache(maxsize=None)
def bfs(one, two, thr):
    if one==two==thr==0:
        return 0
    tmp=1
    if one>0:
        tmp+=bfs(one-1,two,thr)*one/n
    if two>0:
        tmp+=bfs(one+1,two-1,thr)*two/n
    if thr>0:
        tmp+=bfs(one,two+1,thr-1)*thr/n
    
    return tmp*n/(one+two+thr)

print(bfs(lst[0],lst[1],lst[2]))

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(lst[2]+1):
    for j in range(lst[1]+lst[2]+1-k):
        for i in range(lst[0]+lst[1]+lst[2]+1-k-j):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])
### BUGGY CODE ###

n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n+1):
    if cursor[i] < n-1:
      j = table[i][cursor[i]]
      if i not in is_matched and table[j][cursor[j]] == i and j not in is_matched:
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched.clear()
print(d)

### FIXED CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)