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

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    from scipy.optimize import dual_annealing
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = dual_annealing(f, [[min(A), max(A)+1]], maxiter=100)
    #print(res)
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    A = sorted(a - i for i, a in enumerate(A))
    m = A[N//2]
    return sum(abs(a-m) for a in A)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

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

from math import factorial

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

def comb(n, r):
    if n - r < 0:
        return 0
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))

nums = [0] * (N + 1)
for i, v in enumerate(A):
    nums[v] += 1
combs = list(map(lambda n: int(comb(n, 2)), nums))
total = sum(combs)

for k, val in enumerate(A):
    count = comb(nums[val] - 1, 2)
    print(total - combs[val] + count)


### FIXED CODE ###

from math import factorial

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

def comb(n, r):
    if n - r < 0:
        return 0
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))

nums = [0] * (N + 1)
for i, v in enumerate(A):
    nums[v] += 1
combs = list(map(lambda n: comb(n, 2), nums))
total = sum(combs)

for k, val in enumerate(A):
    print(total - (nums[val] - 1))
### BUGGY CODE ###

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

def do_binary_search(target_value, target_list, target_list_length=None):
    left = 0
    right = target_list_length

    while right - left > 0:
        mid = (right + left) / 2
        key = target_list[mid]
        if key == target_value:
            return True
        elif target_value < key:
            right = mid
        else:
            left = mid + 1
    return False



def main():
    s_length = int(raw_input())
    s = [int(x) for x in raw_input().strip().split(' ')]
    t_length = raw_input()
    t = [int(x) for x in raw_input().strip().split(' ')]

    counter = 0
    for value in t:
        # counter += int(do_binary_search(value, s, s_length))
        counter += int(value in s)

    print counter 

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def do_binary_search(target_value, target_list, target_list_length=None):
    left = 0
    right = target_list_length

    while right - left > 0:
        mid = (right + left) / 2
        key = target_list[mid]
        if key == target_value:
            return True
        elif target_value < key:
            right = mid
        else:
            left = mid + 1
    return False



def main():
    s_length = int(raw_input())
    s = [int(x) for x in raw_input().strip().split(' ')]
    t_length = raw_input()
    t = [int(x) for x in raw_input().strip().split(' ')]

    counter = 0
    for value in t:
        counter += int(do_binary_search(value, s, s_length))

    print counter 

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

N = int(input())
next = []
for i in range(N):
    next.append(int(input()))
count = 0
history = [1]
while True:
    light = next[history[-1] - 1]
    if light in history:
        print(-1)
        exit()
    count += 1
    if light == 2:
        print(count)
        exit()
    else:
        history.append(light)

### FIXED CODE ###

N = int(input())
next = []
for i in range(N):
    next.append(int(input()))
count = 0
light = 1
for i in range(N):
    light = next[light - 1]
    count += 1
    if light == 2:
        print(count)
        exit()
print(-1)
### BUGGY CODE ###

# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数を２つのグループに分ける

from collections import defaultdict
import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = defaultdict(lambda : 0)
  #print(c)
  fac[1] = 1
  fac = facto(c, fac)
  #print(fac)
  keys = list((fac.keys()))
  print(len(keys))  
  
def facto(n, fac):
  if n == 1:
    return fac
  cursor = 2
  while True:
    if n % cursor == 0:
      fac[cursor] += 1
      n = n // cursor
      if n == 1:
        break
    else:
      if cursor > 2:
        cursor += 2
      else:
        cursor += 1
      
  return fac
  
def gojo(a,b):
  if b > a:
    a, b = b, a
  c = a % b
  if c == 0:
    return(b)
  else:
    return gojo(b, c)

if __name__ == "__main__":
  main()


### FIXED CODE ###

# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数＋１が答え

import itertools
from fractions import gcd
from math import ceil

def main():
  a, b = map(int, input().split())
  fac = facto(gcd(a,b))
  print(len(fac))  
  
def facto(n):
  fac = [1]
  if n == 1:
    return [1]
  elif n % 2 == 0:
    fac = [1, 2]
    while n % 2 == 0:
      n = n // 2
  
  max_n = ceil(n ** 0.5) + 1
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 2):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n = n // cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
  if n != 1:
    fac.append(n)
  return fac

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

import collections
N=int(input())
S=collections.Counter(input() for i in range(N))
dictionary=sorted(key for key,value in S.items() if value==max(S.values()))
for d in dictionary:
    print(d)

### FIXED CODE ###

import collections
N=int(input())
S=collections.Counter(input() for i in range(N))
maximum=max(S.values())
sort=sorted(key for key,value in S.items() if value==maximum)
for s in sort:
    print(s)
### BUGGY CODE ###

import itertools

n = int(input())
s = str(input())

R = []
G = []
B = []
for i in range(n):
  if s[i] == "R":
    R.append(i+1)
  elif s[i] == "G":
    G.append(i+1)
  else:
    B.append(i+1)

ans = 0
for i in range(len(R)):
  for j in range(len(G)):
    for k in range(len(B)):
      if abs(R[i]-G[j]) != abs(R[i] - B[k]) and abs(R[i]-G[j]) != abs(G[j] - B[k]) and abs(R[i] - B[k]) != abs(G[j] - B[k]):        
        ans += 1

print(ans)  

### FIXED CODE ###

n = int(input())
s = str(input())

R = []
G = []
B = []
for i in range(n):
  if s[i] == "R":
    R.append(i+1)
  elif s[i] == "G":
    G.append(i+1)
  else:
    B.append(i+1)

  
ans = 0

for i in range(len(R)):
  for j in range(len(G)):
    temp = 0
    if 2*R[i] - G[j] >0 and 2*R[i] - G[j] <= n:
      if s[2*R[i] - G[j] -1] == "B":
        temp += 1
    if 2*G[j] - R[i] >0 and 2*G[j] - R[i] <= n:
      if s[2*G[j] - R[i]-1] == "B":
        temp += 1
    if (R[i]+G[j])%2 == 0:
      if s[(R[i]+G[j])//2-1] == "B":
        temp += 1
    ans += len(B)- temp

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

import itertools 
import math
from functools import reduce

num = int(input())
a_list = [i for i in range(1,num+1)]
comb_list = list(itertools.product(a_list, repeat=3))

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

print(sum([gcd_list(x) for x in comb_list]))

### FIXED CODE ###

import itertools 
import math
from functools import reduce


num = int(input())

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

if num<=2:
    a_list = [i for i in range(1,num+1)]
    comb_list = list(itertools.product(a_list, repeat=3))
    print(sum([gcd_list(x) for x in comb_list]))

else:
    a_list = [i for i in range(1,num+1)]
    comb_list = list(itertools.combinations_with_replacement(a_list, 3))
    test = sum([gcd_list(x) for x in comb_list])*3

    comb_list_dup = [[i, i, i] for i in a_list]
    duplica = sum([gcd_list(x) for x in comb_list_dup])*2

    comb_list_unique = list(itertools.combinations(a_list, 3))
    unique = sum([gcd_list(x) for x in comb_list_unique])*3
    print(test-duplica+unique)
### BUGGY CODE ###

import sys
import math
import itertools as it
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
p = intl()
cnt = 0
for i in range(n):
    if p[i] <= min(p[:i+1]):
        cnt += 1
print(cnt)

### FIXED CODE ###

import sys
import math
import itertools as it
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
p = intl()
cnt = 0
m = p[0]
for i in range(n):
    if m > p[i]:
        m = p[i]
    if p[i] <= m:
        cnt += 1
print(cnt)
### BUGGY CODE ###

#input
N, M = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    A[i], B[i] = map(int, input().split())

#output
import heapq

#点数配列の用意
point = 0
hq = []
#M-i日目(1 <= i <= M)に働ける仕事の中で、Bが最大のものを選ぶ
for j in range(0, M):
    for i in range(N):
        if A[i] == j + 1:
            heapq.heappush(hq, -B[i])
    if len(hq):
        point += -heapq.heappop(hq)

print(point)

### FIXED CODE ###

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

jobs = {}
for _ in range(N):
    A, B = map(int, input().split())
    if A > M :
        continue
    if A in jobs:
        jobs[A].append(B)
    else:
        jobs[A] = [B]

#output
import heapq

#点数配列の用意
point = 0
hq = []
#M-i日目(1 <= i <= M)に働ける仕事の中で、Bが最大のものを選ぶ
for A in range(1, M+1):
    if A in jobs:
        for B in jobs[A]:
            heapq.heappush(hq, -B)
    else:
        if len(hq) == 0:
            continue
    point += -heapq.heappop(hq)

print(point)
### BUGGY CODE ###

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

l = abs(N - M)

def factorial(n):
    m = 1
    for i in range(2, n+1):
        m *= i
    return m


# 列を作れないとき
if l >= 2:
    print(0)
    exit()

if l == 1:
    _n = factorial(N)
    _m = factorial(M)
    ans = _n * _m
    print(ans)
    exit()


_n = factorial(N)
_m = factorial(M)

ans = (_n * _m * 2) % (10**9+7)
print(ans)



### FIXED CODE ###

import math

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

l = abs(N - M)

# 列を作れないとき
if l >= 2:
    print(0)
    exit()

if l == 1:

    if N < M:
        _n = math.factorial(N)
        _m = _n * (M)
        ans = _n * _m
        print(ans%(10**9+7))
        exit()

    else:
        _m = math.factorial(M)
        _n = _m * (N)
        ans = _n * _m
        print(ans%(10**9+7))
        exit()



_n = math.factorial(N)
# _m = factorial(M)

ans = (_n * _n * 2) % (10**9+7)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    #print(mi)
    dp = [[False for _ in range(k+1)] for _ in range(n+1)]
    dp[0][0] = True
    for i in range(n):
        for j in range(k+1):
            if i == mi-1:
                dp[i+1][j] = dp[i][j]
            elif j >= a[i]:
                dp[i+1][j] = dp[i][j] | dp[i][j-a[i]]
            else:
                dp[i+1][j] = dp[i][j]

    #print(dp)
    needed = False
    for j in range(max(0, k - a[mi-1]), k):
        if dp[-1][j] == True:
            needed = True
            break

    if needed:
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
for i in range(1,n):
    da[i].append([i-1,0])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

### FIXED CODE ###

import heapq
import numpy as np
import sys

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, [i[1],i[0]])
while(len(pq)):
    now = heapq.heappop(pq)
    if now[1] == n-1:
        print(now[0])
        sys.exit()
    if ju[now[1]]:
        continue
    ju[now[1]] = True
    for i in da[now[1]]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,[now[0]+i[1],i[0]])
print(-1)
### BUGGY CODE ###

H,W = map(int,input().split())
S = [list(input()) for i in range(0,H,1)]

teraseru_H = [[0 for i in range(0,W,1)]for j in range(0,H,1)]
teraseru_W = [[0 for i in range(0,W,1)]for j in range(0,H,1)]

left = -1
for i in range(0,H,1):
    left=-1
    for j in range(0,W,1):
        if S[i][j]=="#":
            if left!=-1:
                for k in range(left,j,1):
                    teraseru_H[i][k] = j-left
                left=-1

        else:#"."
            if left==-1:
                left=j
    if left!=-1:
        for k in range(left,W,1):
            teraseru_H[i][k] = W-left
    left=-1

left = -1
for j in range(0,W,1):
    left=-1
    for i in range(0,H,1):
        if S[i][j]=="#":
            if left!=-1:
                for k in range(left,i,1):
                    teraseru_W[k][j] = i-left
                left=-1
        else:#"."
            if left==-1:
                left=i
    if left!=-1:
        for k in range(left,H,1):
            teraseru_W[k][j] = H-left
    left=-1

ans = 0

for i in range(0,H,1):
    for j in range(0,W,1):
        ans = max(ans,teraseru_H[i][j]+teraseru_W[i][j]-1)
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [list(input()) for i in range(0,H,1)]

teraseru_H = [[0 for i in range(0,W,1)]for j in range(0,H,1)]
teraseru_W = [[0 for i in range(0,W,1)]for j in range(0,H,1)]

left = -1
for i in range(0,H,1):
    left=-1
    for j in range(0,W,1):
        if S[i][j]=="#":
            if left!=-1:
                for k in range(left,j,1):
                    teraseru_H[i][k] = j-left
                left=-1

        else:#"."
            if left==-1:
                left=j
    if left!=-1:
        for k in range(left,W,1):
            teraseru_H[i][k] = W-left
    left=-1

left = -1
for j in range(0,W,1):
    left=-1
    for i in range(0,H,1):
        if S[i][j]=="#":
            if left!=-1:
                for k in range(left,i,1):
                    teraseru_W[k][j] = i-left
                left=-1
        else:#"."
            if left==-1:
                left=i
    if left!=-1:
        for k in range(left,H,1):
            teraseru_W[k][j] = H-left
    left=-1

ans = 0

for i in range(0,H,1):
    for j in range(0,W,1):
        ans = max(ans,teraseru_H[i][j]+teraseru_W[i][j]-1)
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
R,G,B = [],[],[]
for i, char in enumerate(S):
    if char == 'R':
        R.append(i+1)
    if char == 'G':
        G.append(i+1)
    if char == 'B':
        B.append(i+1)
        
ans = len(R)*len(G)*len(B)
for i in R:
    for j in G:
        for k in B:
            L = sorted([i,j,k])
            if L[0]+L[2]==2*L[1]:
                ans -= 1
            
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
R = S.count('R')
G = S.count('G')
B = S.count('B')
ans = R*G*B
for i in range(N):
    for d in range(N):
        j = i + d
        k = i + 2*d
        if k >= N:
            break
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

A,B,K = map(int,input().split())
for i in range(K):
    if(A >= 1):
        A -= 1
    elif(B >= 1):
        B -= 1
print(A, B)

### FIXED CODE ###

A,B,K = map(int,input().split())
if(K <= A):
    A = A-K
elif(K < A+B):
    B = A+B-K
    A = 0
else:
    A = 0
    B = 0
print(A, B)
### BUGGY CODE ###

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

    for _ in range(q):
        l = []
        b, c = map(int, input().split())
        l = [i if i != b else c for i in a]
        print(sum(l))
        a = l[:]


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = Counter(a)
    q = int(input())
    s = sum(a)
    for _ in range(q):
        b, c = map(int, input().split())
        s -= cnt[b]*b

        s += cnt[b]*c
        cnt[c] += cnt[b]
        cnt[b] = 0
        print(s)

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

a,b,q=map(int,input().split())
S,T=[],[]
for i in range(a):
  S.append(int(input()))
for i in range(b):
  T.append(int(input()))
def f(list,n):
  if n<list[0]:
    return [-float("inf"),list[0]]
  elif list[-1]<n:
    return [list[-1],float("inf")]
  else:
    flag,count=0,0
    l=len(list)
    i=(l-1)//2
    while flag==0:
      if list[i]<n<list[i+1]:
        flag=1
        return [list[i],list[i+1]]
      elif n<list[i]:
        i//=2
        count+=1
      else:
        i+=(l-1)//(2**(count+1))
        count+=1
def g(SS,TT,x):
  a,b,c,d=x-SS[0],SS[1]-x,x-TT[0],TT[1]-x
  dis1=max(a,c)
  dis2=min(2*a+d,2*d+a)
  dis3=max(b,d)
  dis4=min(2*b+c,2*c+b)
  return min([dis1,dis2,dis3,dis4])
        
for i in range(q):
  x=int(input())
  print(g(f(S,x),f(T,x),x))

### FIXED CODE ###

import bisect
a,b,q=map(int,input().split())
S,T=[],[]
for i in range(a):
  S.append(int(input()))
for i in range(b):
  T.append(int(input()))
def f(list,n):
  if n<list[0]:
    return [-float("inf"),list[0]]
  elif list[-1]<n:
    return [list[-1],float("inf")]
  else:
    i=bisect.bisect_left(list,n)
    return [list[i-1],list[i]]
def g(SS,TT,x):
  a,b,c,d=x-SS[0],SS[1]-x,x-TT[0],TT[1]-x
  dis1=max(a,c)
  dis2=min(2*a+d,2*d+a)
  dis3=max(b,d)
  dis4=min(2*b+c,2*c+b)
  return min([dis1,dis2,dis3,dis4])
for i in range(q):
  x=int(input())
  print(g(f(S,x),f(T,x),x))
### BUGGY CODE ###

import sys

limit = 1E18
n = int(input())
total = 1
# A string
line = str(input())

if line.startswith("0 ") or " 0" in line:
    print(0)
    exit()

for i in line.split():
    x = int(i)
    total *= x

print(-1 if total > limit else total)

### FIXED CODE ###

limit = 1E18
n = int(input())
total = 1
# A string
line = str(input())

if line.startswith("0 ") or " 0" in line:
    print(0)
    exit()

for i in line.split():
    x = int(i)
    total *= x
    if total > limit:
        print(-1)
        exit()

print(-1 if total > limit else total)
### BUGGY CODE ###

N=int(input())
list = list(map(int, input().split()))
res = []
i=1

for i in range(1,N+1):
  res.append(list.count(i))
  i+=1

j=0
for j in range(0,len(res)):
  print(str(res[j]))
  j+=1

### FIXED CODE ###

from collections import Counter

N=int(input())
list = list(map(int, input().split()))
i=1
counter = Counter(list)

for i in range(1,N+1):
  print(counter[i])
### BUGGY CODE ###

def main():
    N = int(input())
    A = []
    for i in range(N):
        A.append(int(input()))
    
    for i in range(N):
        tmp,A[i] = A[i],0
        print(max(A))
        A[i] = tmp


if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = []
    for i in range(N):
        A.append(int(input()))
    
    max_A = max(A)
    B = sorted(A)
    max2_A = B[N-2]

    if max_A == max2_A:
        for i in range(N):
            print(max_A)
        exit()
    
    for i in range(N):
        tmp=A[i]
        if tmp == max_A:
            print(max2_A)
        else:
            print(max_A)

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

n, q = (int(_) for _ in input().split())
l = [list(map(int, input().split())) for i in range(n-1)]
p = [list(map(int, input().split())) for i in range(q)]
l = sorted(l,key = lambda x:(x[0] ,x[1]))

res = [0] * n
for i in p:
    res[i[0]-1] += i[1]
for i in l:
    res[i[1]-1] += res[i[0]-1]

[print(i,end=" ") for i in res]
print()

### FIXED CODE ###

n, q = (int(_) for _ in input().split())
res = [0] * n
l = [[] for i in range(n-1)]
for i in range(n-1):
    a, b = (int(_) for _ in input().split())
    l[a-1].append(b)
p = [list(map(int, input().split())) for i in range(q)]

for i in p:
    res[i[0]-1] += i[1]
for i in range(n-1):
    for ii in l[i]:
        res[ii-1] += res[i]

[print(i,end=" ") for i in res]
print()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(1,n):
    for j in range(i):
        if a[i] + a[j] == abs(i-j):
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dic = {}
ans = 0
for i in range(n):
    r = i -a[i]
    ans += dic.get(r, 0)
    l = a[i] + i
    dic[l] = dic.get(l, 0) + 1
print(ans)