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

from functools import reduce
from bisect import bisect

def soinsuu_bunkai(n):
    ret = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            ret[p]= ret[p]+1 if p in ret else 1
            n //= p
        p += 1
    if n != 1:
        ret[n] = 1
    return ret   
    
def make_triangle(n):
    lst = []
    sum_ = 0
    for i in range(1,n+1):
        sum_ += i
        lst.append(sum_)
    return lst    

N = int(input())
dic = soinsuu_bunkai(N)
lst = make_triangle(N)
#print(lst)
#print(dic)
ans = 0
for k,v in dic.items():
    b = bisect(lst,v)
    #print(b)
    ans += b
print(ans)    


### FIXED CODE ###

from functools import reduce
from bisect import bisect

def soinsuu_bunkai(n):
    ret = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            ret[p]= ret[p]+1 if p in ret else 1
            n //= p
        p += 1
    if n != 1:
        ret[n] = 1
    return ret   
    
def make_triangle(n):
    cnt = 0
    sum_ = 0
    for i in range(1,n+1):
        sum_ += i
        if sum_ > n:
            break
        else:
            cnt += 1
    return cnt    

dic = soinsuu_bunkai(int(input()))
ans = 0
for k,v in dic.items():
    ans += make_triangle(v)  
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
x=[]
for i in range(a, b):
    for j in range(i+1, b+1):
        x.append((i*j)%2019)
print(min(x))

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
if b-a>=673:
    print(0)
else:
    x=[]
    for i in range(a, b):
        for j in range(i+1, b+1):
            x.append((i*j)%2019)
    print(min(x))
### BUGGY CODE ###

s=[int(i) for i in input()]
n=len(s)
updated=True
while updated:
    updated=False
    for i in range(len(s)-1):
        if s[i] != s[i+1]:
            del s[i]
            del s[i]
            updated=True
            break

print(n-len(s))


### FIXED CODE ###

s=input()

stack=[]
for si in s:
    stack.append(si)
    if len(stack) >= 2 and stack[-1] != stack[-2]:
        del stack[-1]
        del stack[-1]
print(len(s)-len(stack))
### BUGGY CODE ###

n = int(input())
strs = [sorted(str(input())) for _ in range(n)]

cnt = 0
while len(strs) > 1:
  s = strs.pop()
  cnt += strs.count(s)
print(cnt)

### FIXED CODE ###

n = int(input())
strs = ["".join(sorted(str(input()))) for _ in range(n)]

cache = {}
cnt = 0
for s in strs:
  if s in cache.keys():
    cnt = cnt + cache[s]
    cache[s] = cache[s] + 1
  else:
    cache[s] = 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
h = a[0] // 2
count = 1
while True:
    if h in a and h != a[0]:
        print(a[0], h)
        break
    else:
        if count % 2 == 1:
            h += count
        else:
            h -= count
    count += 1

### FIXED CODE ###

import numpy as np


def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]


n = int(input())
a = list(map(int, input().split()))
ma = max(a)
h = getNearestValue(a, ma//2)
if h == ma:
    h = 0
print(ma, h)
### BUGGY CODE ###

#!/usr/bin/env python3 ## -*- python -*-

def main():
    s = []
    s.append(input())
    q = int(input())
    head = "l"
    for i in range(q):
        d = input()
        if d[0] == "1":
            if head == "l":
                head = "r"
            else:
                head = "l"
        else: # 2
            dd = d.split()
            f = int(dd[1])
            c = dd[2]
            if f == 1:
                if head == "l":
                    s.insert(0,c)
                else:
                    s.append(c)
            else: # f == 2
                if head == "l":
                    s.append(c)
                else:
                    s.insert(0,c)

    ans = ''.join(s)
    if head == "r":
        ans = ans[::-1]
    print(ans)
main()

### FIXED CODE ###

#!/usr/bin/env python3 ## -*- python -*-
from collections import deque

def main():
    s = deque()
    s.extend(input())
    q = int(input())
    head = "l"
    for i in range(q):
        d = input()
        if d[0] == "1":
            if head == "l":
                head = "r"
            else:
                head = "l"
        else: # 2
            dd = d.split()
            f = int(dd[1])
            c = dd[2]
            if f == 1:
                if head == "l":
                    s.appendleft(c)
                else:
                    s.append(c)
            else: # f == 2
                if head == "l":
                    s.append(c)
                else:
                    s.appendleft(c)

    if head == "r":
        s.reverse()
    ans = ''.join(s)
    print(ans)
main()
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
for i in range(m):
    k = np.argmax(a)
    if a[k] == 0:
        break
    a[k] = int(a[k]/2)
ans = sum(a)
print(ans)


### FIXED CODE ###

#import numpy as np
import sys
import heapq #優先度付きキュー
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
a = [int(i)*(-1) for i in input().split()] #各要素*(-1)
heapq.heapify(a)
for i in range(m):
    """
    k = np.argmax(a)
    if a[k] == 0:
        break
    a[k] = int(a[k]/2)
    """
    tmp = heapq.heappop(a) #最小値を抜き取る(最大値*(-1)を抜き取る）
    heapq.heappush(a, (-1)*(-tmp//2)) #要素を追加
ans = -sum(a)
print(ans)
### BUGGY CODE ###

from collections import Counter
from math import factorial
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n=int(input())
s=[0]*n
dic={}
group={}
ans=0
dic2=[0]*n
for i in range(n):
    s[i]=sorted(input())
    dic[i]=str(Counter(s[i]))
    dic2[i]=dic[i]
group=Counter(dic2)

for i in list(group):
    if group[i]==1:
        continue
    ans+=cmb(group[i],2)
print(ans)


### FIXED CODE ###

from collections import Counter

N = int(input())
a=[]
for i in range(N):
    s=input()
    S=[]
    for j in range(10):
        S.append(s[j])
    S.sort()
    s="".join(S).split()
    a.append(s[0])
x=Counter(a)
num=x.values()
#print(list(num))
ans=0
for i in (list(num)):
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

# 177 C
N = int(input())
A = list(map(int, input().split()))
ans = 0
mod = 10**9+7
for i in range(len(A)-1):
    for j in range(i+1, len(A)):
        ans += A[i]*A[j]%mod
print(ans%mod)

### FIXED CODE ###

# 177 C
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

sq_sum = sum(map(lambda x: x*x, A))
sum_sq = sum(A) * sum(A)
answer = (sum_sq - sq_sum) // 2

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



N=int(input())

S_list = []
S_count = []
max = 1
for i in range(N):
    s = input()
    if s in S_list:
        index = S_list.index(s)
        #S_count.append(S_count[index]+1)
        S_count[index] += 1
        if max < S_count[index]:
            max = S_count[index]
    else:
        S_list.append(s)
        S_count.append(1)
        #if max < S_count[i]:
        #    max = S_count[i]
     
#print(S_list)
#print(S_count)
#print(max)
S_max = []
for j in range(len(S_list)):
    if S_count[j] == max:
        S_max.append(S_list[j])

S_max.sort()
for k in range(len(S_max)):
    print(S_max[k])

### FIXED CODE ###



N=int(input())

S_list = []
S_count = []
max = 1
temp_list = []
#for i in range(N):
#    s = input()
#    temp_list.append(s)
S_dict = {}
for i in range(N):
    s = input()
    if s in S_dict.keys():
        S_dict[s] += 1
        if max < S_dict[s]:
            max = S_dict[s]
    else:
        S_dict[s] = 1
    
     
#print(S_list)
#print(S_count)
#print(max)
S_max = []
for j in S_dict:
    if S_dict[j] == max:
        S_max.append(j)

S_max.sort()
for k in range(len(S_max)):
    print(S_max[k])
### BUGGY CODE ###

N = int(input())

goods = []

for i in range(N):
    S = input()
    if S not in goods:
        goods.append(S)

print(len(goods))    


### FIXED CODE ###

from collections import defaultdict

N = int(input())

goods = defaultdict(lambda: 0)

for i in range(N):
    S = input()
    goods[S] = 0

print(len(goods))
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    Card = [[] for i in range(M)]
    Diff = [i for i in range(1, N + 1)]

    for i in range(0, M):
        L, R = map(int, input().split())
        tmp = []
        for j in range(L, R + 1):
            if j in Diff:
                tmp.append(j)
        Diff = tmp
    print(len(Diff))    


main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    L =[0 for i in range(M)]
    R = [0 for i in range(M)]

    for i in range(0, M):
        L[i], R[i] = map(int, input().split())
    
    print(max(min(R) - max(L) + 1, 0))


main()
### BUGGY CODE ###

string = input()
nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)
d = int(input())

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = int(not bool(s))
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt
# print(mod(dfs() - 1))

for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = int(not bool(s))
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

# print(dp[0][0][1] - 1)
# print(dp)
# for i in dp:
#     for s in i:
#         for border in s:
#             print(border, end=" ")
#         print()
#     print("-----")

def count(v):
    cnt = 0
    while v:
        cnt += v % 10
        v //= 10
    return cnt

ans = 0
for i in range(1, k + 1):
    if count(i) % d == 0:
        ans += 1
print(ans)


### FIXED CODE ###

string = input()
d = int(input())

nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = int(not bool(s))
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt
# print(mod(dfs() - 1))

for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = int(not bool(s))
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

print(mod(dp[0][0][1] - 1 + M))
### BUGGY CODE ###

a, b, k = map(int, input().split())

for i in range(a, b + 1):
    if i < a + k or i > b - k:
        print(i)


### FIXED CODE ###

a, b, k = map(int, input().split())

if b - a + 1 <= k * 2:
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, a + k):
        print(i)
    for i in range((b - k + 1), (b + 1)):
        print(i)
### BUGGY CODE ###

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

n, m = map(int, input().split())
a = list( map(int, input().split()))
a_modm=[ai%m for ai in a]

from itertools import accumulate
B = [0] + a_modm
B = list(accumulate(B))
ans = 0
for i in range(n):
    for j in range(i,n):
        if (B[j+1]%m-B[i]%m)%m == 0:
            ans+=1

print(ans)


### FIXED CODE ###

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

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

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

from itertools import accumulate
b = [0] + a
b = list(accumulate(b))

count_mod = defaultdict(int)

for i in range(n+1):
    bi_modm = b[i]%m
    if count_mod[bi_modm] is None: count_mod[bi_modm]=1
    else: count_mod[bi_modm] += 1

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

N,K=map(int,input().split())
p=list(map(int,input().split()))
E=[]
for i in range(N):
  E.append((1+p[i])/2)
Max_E=0
for i in range(K):
  Max_E=Max_E+E[i]
for i in range(1,N-K+1):
  A=0
  for j in range(i,i+K):
    A=A+E[j]
  if A>Max_E:
    Max_E=A
print(Max_E)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
p=list(map(int,input().split()))
E=[]
for i in range(N):
  E.append((1+p[i])/2)
S=np.cumsum(E)
max=0
if N!=K:
  for i in range(N-K+1):
    if S[i+K-1]-S[i-1]>max:
       max=S[i+K-1]-S[i-1]
  print(max)
else:
  print(sum(E))
### BUGGY CODE ###

N = input()
S = list(input())

min_num = 300000
left = 0

for i in range(len(S)):

  if i > 0:
    left += int(S[i - 1] == "W")

  right = S[i+1: ].count("E")

  if left + right < min_num:
    min_num = left + right

print(min_num)


### FIXED CODE ###

N = input()
S = list(input())

length = len(S)
min_num = 300000
left = 0
right = S.count("E")

for i in range(length):

  if i > 0:
    left += int(S[i - 1] == "W")

  if i < length:
    right -= int(S[i] == "E")

  if left + right < min_num:
    min_num = left + right

print(min_num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from heapq import *

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
pq = []
heappush(pq, (-A[0]*2, 0, 0))
ans = 0

for _ in range(M):
    s, i, j = heappop(pq)
    #print(s, i, j)
    s *= -1
    ans += s
    
    if i==j:
        if j<N-1:
            heappush(pq, (-A[i]-A[j+1], i, j+1))
    elif i<j:
        if i+1==j:
            heappush(pq, (-A[i+1]-A[j], i+1, j))
        
        if j<N-1:
            heappush(pq, (-A[i]-A[j+1], i, j+1))
            
        heappush(pq, (-A[i]-A[j], j, i))

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import *

def judge(x):
    cnt = 0
    
    for i in range(N):
        idx = bisect_left(A, x-A[i])
        cnt += N-idx
    
    return cnt>=M
    
def binary_search():
    l, r = 0, 10**11
    
    while l<=r:
        mid = (l+r)//2
        
        if judge(mid):
            l = mid+1
        else:
            r = mid-1
    
    return r

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
border = binary_search()
acc = [0]

for Ai in A:
    acc.append(acc[-1]+Ai)

ans = 0
cnt = 0

for i in range(N):
    idx = bisect_left(A, border-A[i]+1)
    ans += A[i]*(N-idx)+acc[N]-acc[idx]
    cnt += N-idx

ans += (M-cnt)*border

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

import fractions

n=int(input())
al=input().split()
al_i = [int(s) for s in al]
m = max(al_i)
gm = 0

for x in range(n):
   t = al_i[x]
   al_i[x] = m
   g = al_i[0]
   for y in range(n):
      g = fractions.gcd(g,al_i[y]) 
   al_i[x] = t
   if g>gm:
      gm = g
print(gm)


### FIXED CODE ###

import sys

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(max(al_i[0],al_i[1]))
   sys.exit()

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n-1):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))



def f(c1, c2, c3):
    if min(c1, c2, c3) < 0:
        return 0
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    p1 = c1 / N
    ret += f(c1-1, c2, c3) * p1 / ip0
    p2 = c2 / N
    ret += f(c1+1, c2-1, c3) * p2 / ip0
    p3 = c3 / N
    ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret

N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
idx = N//2-1
for i in range(N):
    tmp = X[:i] + X[i+1:]
    tmp.sort()
    print(tmp[idx])

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
mid = N//2-1
sX = sorted(X)
for i in range(N):
    if X[i] <= sX[mid]: print(sX[mid+1])
    else: print(sX[mid])
### BUGGY CODE ###

import numpy as np

n = int(input())

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

for i in range(n-1):
  for j in range(i+a[i]+1, n):
    if j-i == a[i] + a[j]:
      ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())

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

x = {}
y = {}

ans = 0

for i in range(n):
  x.setdefault((i+a[i]), []).append(i) 
  y.setdefault((i-a[i]), []).append(i)

z = list(set(x.keys()) & set(y.keys()))

# print(x)
# print(y)
# print(z)

for i in z:
  if x[i][len(x[i])-1] < y[i][0]:
    n = len(y[i]) * len(x[i])
    ans += n
    # print(x[i])
    # print(y[i])
    # print(n)
    # print(ans)

  else:
    for j in range(len(x[i])):
      # print(x[i])
      # print(x[i][j])
      # print(y[i])
      ans += sum(1 for k in y[i] if x[i][j] < k)

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

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

if '0' in a:
    s = 0
else:
    for i in range(n):
        s = s * a[i]
if s > 10 ** 18:
    s = -1
print(s)

### FIXED CODE ###

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

if 0 in a:
    s = 0
else:
    for i in range(n):
        s = s * a[i]
        if s > 10 ** 18:
            s = -1
            break
print(s)
### BUGGY CODE ###

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

L = [N]
c = 2
while c < N**0.5:
    if L[-1] != N//c:
        L.append(N//c)
    c += 1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp1 = [0 for _ in range(c+len(L))]
dp2 = [0 for _ in range(c+len(L))]

for j in range(1, c+1):
    dp1[j] = N//j
for j in range(1, len(L)):
    dp1[j+c] = N//L[j]*(L[j]-L[j-1])

for i in range(2, K):
    if i%2 == 0:
        dp2[-1] = dp1[1]
        for j in range(2, c+len(L)):
            dp2[c+len(L)-j] = dp2[c+len(L)-j+1]+dp1[j]
        for j in range(1, len(L)):
            dp2[j+c] *= (L[j]-L[j-1])
    else:
        dp1[-1] = dp2[1]
        for j in range(2, c+len(L)):
            dp1[c+len(L)-j] = dp1[c+len(L)-j+1]+dp2[j]
        for j in range(1, len(L)):
            dp1[j+c] *= (L[j]-L[j-1])

if K%2 == 0:
    ans = sum(dp1)
else:
    ans = sum(dp2)

print(ans%(10**9+7))

### FIXED CODE ###

from itertools import accumulate

N,K = map(int, input().split())
mod = 10**9+7
sqt = int(N**0.5)
cnt = [N // i-N // (i+1) for i in range(1, N//sqt)] + [1]*sqt
x = cnt
for _ in range(K):
    x = [(i*j)%mod for i, j in zip(accumulate(reversed(x)), cnt)]
    

print(x[-1])
### BUGGY CODE ###

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

count = 0
for i in range(n-1):
    for j in range(i+1,n):
        if (j-i) == (a_l[j] + a_l[i]):
            count += 1

print(count)



### FIXED CODE ###

n = int(input())
a_l = list(map(int,input().split()))
ia = list(enumerate(a_l))

x_dict = {}
y_dict = {}
for i, a in ia:
    x = i+a
    y = i-a
    if x in x_dict:
        x_dict[x] += 1
    else:
        x_dict[x] = 1
    if y in y_dict:
        y_dict[y] += 1
    else:
        y_dict[y] = 1

count = 0
for xkey in x_dict.keys():
    if xkey in y_dict:
        count += x_dict[xkey] * y_dict[xkey]

print(count)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    A.sort()

    if N == 1:
        print(1)
        return
    if A[0] == 1:
        print(0 if A[1] == 1 else 1)
        return

    ax = set()
    ans = 0
    for i in range(1, N):
        a0 = A[i-1]

        for x in ax:
            if a0 % x == 0:
                break
        else:
            if a0 == A[i]:
                ax.add(a0)
                continue
            ax.add(a0)
            ans += 1

    a0 = A[-1]
    for x in ax:
        if a0 % x == 0:
            break
    else:
        ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
        #print(dp)
    print(dp.count(1))


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

n = int(input())
def stairs(n):
    if (n == 1):
        return 1
    elif(n == 2):
        return 2
    elif(n == 3):
        return 4
    return stairs(n-1) + stairs(n-2) + stairs(n-3)
while (n != 0):
    pn = stairs(n)
    if (pn%10 == 0):
        pn //= 10
    else:
        pn = pn//10 + 1

    if (pn%365 == 0):
        pn //= 365
    else:
        pn = pn//365 + 1
    print(pn)
    n = int(input())


### FIXED CODE ###

n = int(input())
st = [1,2,4]
for i in range(n-3):
    s = st[-1] + st[-2] + st[-3]
    st.append(s)
while (n != 0):
    pn = st[n-1]
    if (pn%10 == 0):
        pn //= 10
    else:
        pn = pn//10 + 1

    if (pn%365 == 0):
        pn //= 365
    else:
        pn = pn//365 + 1
    print(pn)
    n = int(input())
    st = [1,2,4]
    for i in range(n-3):
        s = st[-1] + st[-2] + st[-3]
        st.append(s)