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

from collections import Counter
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    d = Counter(A)
    # print(d)

    for i in range(Q):
        ans = 0
        b, c = map(int, input().split())
        if b in d.keys():
            d[c] += d[b]
            d[b] = 0
        for k, v in d.items():
            ans += k * v
        # print(d)
        print(ans)


if __name__ == "__main__":
    main()



### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    d = Counter(A)
    # print(d)
    ans = sum(A)

    for i in range(Q):
        b, c = map(int, input().split())
        if d[b] != 0:
            ans -= d[b] * b
            ans -= d[c] * c
            d[c] += d[b]
            d[b] = 0
            ans += d[c] * c

        print(ans)


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

import numpy as np
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_ar = np.array(A_list)
for i in range(M):
    max_pos = np.argmax(A_ar)
    A_ar[max_pos] = A_ar[max_pos]//2
print(sum(A_ar))



### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A_list = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A_list)
for i in range(M):
    max_num = heapq.heappop(A_list) * (-1)
    heapq.heappush(A_list, (-1) * (max_num // 2))
print((-1) * sum(A_list))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

inf = float('inf')

N = int(input())
S = input()

dp = [[-inf] * N for _ in range(N)]

def rec(i, j):
    if not (0 <= i < j < N):
        return 0
    if dp[i][j] != -inf:
        return dp[i][j]
    res = 0
    if S[i] == S[j] and i + rec(i+1, j+1) < j:
        res = max(res, rec(i+1, j+1) + 1, rec(i+1, j), rec(i, j+1))
    else:
        res = max(res, rec(i+1, j), rec(i+1, j))
    dp[i][j] = res
    return res

ans = 0

for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, rec(i, j))

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

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

for i in range(N-2, -1, -1):
    for j in range(N-1, i, -1):
        if S[i] == S[j]:
            dp[i][j] = min(dp[i+1][j+1] + 1, j-i)
        else:
            dp[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, dp[i][j])

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

n,m=map(int,input().split())
id=[0]*100010
for i in range(m):
    ll,rr=input().split()
    for j in range(int(ll),int(rr)+1):
        id[j]+=1

cnt=0
for i in range(1,n+1):
    if id[i]==m:
        cnt+=1
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
maxl,minr=0,n
for i in range(m):
    l,r=map(int,input().split())
    maxl=max(maxl,l)
    minr=min(minr,r)
print(max(0,minr-maxl+1))
### BUGGY CODE ###

# 尺取り法を使って数える

import bisect

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

YZ = Y*Z
BC = []
for b in B:
  for c in C:
    BC.append(b+c)

BC.sort()
# 2つのリストから1つずつ要素を取り出したときに和がx以上となる組合せ
def count_large_2(L1, L2, x):
  L1.sort()
  L2.sort(reverse=True)
  N1, N2 = len(L1), len(L2)
  i = j = 0
  c = 0
  while i<N1 and j<N2:
    if L1[i]+L2[j] >= x:
      c += 1
      j += 1
      if j >= N2:
        c += (N1-i-1) * N2
    else:
      i += 1
      if i>=N1:
        continue
      c += j
  return c


def check(S):
  c = count_large_2(A, BC, S)  
  return c >= K



Sl = 0
Sr = A[0]+B[0]+C[0]+1

while Sr - Sl > 1:
  mid = (Sl + Sr) // 2
  if check(mid):
    Sl = mid
  else:
    Sr = mid


Ans = []
for a in A:
  for b in B:
    if a + b + C[0] < Sr:
      break
    for c in C:
      if a + b + c >= Sr:
        Ans.append(a+b+c)
      else:
        break

Ans.sort(reverse=True)
Ans = Ans + [Sl]*(K-len(Ans))
for ans in Ans:
  print(ans)

### FIXED CODE ###

import bisect

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

YZ = Y*Z
BC = []
for b in B:
  for c in C:
    BC.append(b+c)

BC.sort()
def check(S):
  count = 0
  left = X*Y*Z
  for a in A:
    count += YZ - bisect.bisect_left(BC, S-a)
    left -= YZ
    if count >= K or count+left < K:
      break
  
  return count >= K



Sl = 0
Sr = A[0]+B[0]+C[0]+1

while Sr - Sl > 1:
  mid = (Sl + Sr) // 2
  if check(mid):
    Sl = mid
  else:
    Sr = mid

Ans = []
for a in A:
  for b in B:
    if a + b + C[0] < Sr:
      break
    for c in C:
      if a + b + c >= Sr:
        Ans.append(a+b+c)
      else:
        break

Ans.sort(reverse=True)
Ans = Ans + [Sl]*(K-len(Ans))
for ans in Ans:
  print(ans)
### BUGGY CODE ###

import math

N = int(input())

f_x = 0
sum = 0


for i in range(1,N+1):
    for j in range(1,int(math.floor(i+1)/2)+1):
        if i%j == 0:
            f_x += 1
    sum += i*(f_x+1)
    f_x = 0

print(sum-1)

### FIXED CODE ###

N = int(input())

sum = 0

for j in range(1,N+1):
    k = N//j
    sum += (1+k)*k*j//2
print(sum)
### BUGGY CODE ###

from fractions import gcd

import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    B = []
    C = []

    ok = True
    for a in A:
        c = 0
        while a%2 == 0:
            a //= 2
            c += 1
        B.append(a)
        if C:
            if c != C[-1]:
                ok = False
                break
        C.append(c)

    if not ok:
        print(0)
    else:
        g = 1
        for b in B:
            l = gcd(g, b)
            g = g*b//l
        p = g*2**(c-1)
        ans = (M+p)//(2*p)
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd

import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    B = []

    ok = True
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        B.sort()
        g = 1
        for b in B:
            l = gcd(b, g)
            g = g*b//l
            if g > M:
                ok = False
                break
        if not ok:
            print(0)
        else:
            p = g*2**(c-1)
            ans = (M+p)//(2*p)
            print(ans)


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

mod = pow(10,9)+7
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]+[mod]
DP = [1]
for i in range(1,N+1):
    if i==A[0]:
        DP.append(0)
        A = A[1:]
    else:
        a = DP[i-1]
        b = DP[i-2] if i>1 else 0
        DP.append((a+b)%mod)
print(DP[N]%mod)


### FIXED CODE ###

import bisect
def f(x,a):
  global M
  b = bisect.bisect_left(a,x)
  if x==a[min(b,M)]:
    return True
  else:
    return False
MOD = 10**9+7
N,M = map(int,input().split())
a = [-1]+[int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)
### BUGGY CODE ###


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=[]
S_count=dict()
fixed_count=dict()
for n in range(N):
    s=input()
    s=''.join(sorted(s))
    if s in S:
        S_count[s]+=1
    else:
        S_count[s]=1
    S.append(s)

for k in S_count.keys():
    if S_count[k]>1:
        fixed_count[k]=S_count[k]

key=fixed_count.keys()

total=0

for k in key:
    t=S_count[k]
    if t>=2:
        total+=cmb(t,2)

print(total)

### FIXED CODE ###


N=int(input())
S=[]
total=0

for s in range(N):
    tmp=input()
    S.append("".join(sorted(tmp)))

S=sorted(S)
S_key=list(set(S))
count=[0]*len(S_key)
S_dict=dict(zip(S_key,count))


for s in S:
    total+=S_dict[s]
    S_dict[s]+=1

print(total)
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List
import array
import numpy as np

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: array[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList = np.zeros(W, dtype="int32")
    rowSumList = np.zeros(H, dtype="int32")

    maxColumnSum = 0
    maxColumIndexList: array[int] = []
    maxRowSum = 0
    maxRowIndexList: array[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

import math

K=int(input())
ans=0
for i in range(1,K+1,1):
    for j in range(1,K+1,1):
        for k in range(1,K+1,1):
            a = math.gcd(i,j)
            b = math.gcd(a,k)
            ans += b
print(ans)            

### FIXED CODE ###

import math

N=int(input())
ans=0
for i in range(1,N+1,1):
    for j in range(i,N+1,1):
        for k in range(j,N+1,1):
            list =[i,j,k]
            ff=len(set(list))
            a = math.gcd(i,j)
            b = math.gcd(a,k)
            if ff == 1:
                ans += b
            elif ff == 2:
                ans += 3*b
            else:
                ans += 6*b
print(ans)
### BUGGY CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()


### FIXED CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

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

N, Q = map(int, input().split())
S = input()
L = []
R = []
# ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
flag = []
for i in range(N-1):
	if S[i] == 'A' and S[i+1] == 'C':
		flag.append(1)
		i += 1
	else:
		flag.append(0)
# print(flag)


for i in range(Q):
	print(sum(flag[L[i]-1:R[i]-1]))

# for i in range(Q):
# 	print(ans[i])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = []
R = []
# ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
sum = [0] * (N+1)
for i in range(1, N):
	if S[i-1] == 'A' and S[i] == 'C':
		sum[i+1] = sum[i] + 1
	else:
		sum[i+1] = sum[i]
# print(sum)


for i in range(Q):
	print(sum[R[i]] - sum[L[i]])
### BUGGY CODE ###

#
import sys
import math

# ひとつ入力
n = int(input())

# initial state
a = [int(i) for i in input().split()] 
# last state
b = [int(i) for i in input().split()] 

answer = 0
answer_p = -1
while answer >= 0:
    answer_p = answer
    max_diff=0
    max_diff_i=-1
    for i in range(n):
        diff = b[i] - a[i]
        if max_diff < diff:
            max_diff = diff
            max_diff_i = i
        if b[i] < 1:
            print(-1)
            exit()
    if max_diff < 0:
        print(-1)
        exit()
    elif max_diff==0:
        for i in range(n):
            if b[i] != a[i]:
                print(-1)
                exit()
        print(answer)
        exit()
    else:
        if max_diff_i==n-1:
            res = (b[n-1]-a[n-1]) // (b[0]+b[n-2])
            answer += res
            b[n-1] -= res * (b[0]+b[n-2])
        else:
            res = (b[max_diff_i]-a[max_diff_i]) // (b[max_diff_i+1]+b[max_diff_i-1])
            answer += res
            b[max_diff_i] -= res * (b[max_diff_i+1]+b[max_diff_i-1])
    if answer == answer_p:
        print(-1)
        exit()
#    print(a,b,max_diff,max_diff_i)




### FIXED CODE ###

#
import sys
import math

# ひとつ入力
n = int(input())

# initial state
a = [int(i) for i in input().split()] 
# last state
b = [int(i) for i in input().split()] 

answer = 0
answer_p = -1
while answer >= 0:
    answer_p = answer
    for i in range(n):
        tmp = b[(i-1)%n] + b[(i+1)%n]
        if 0 < tmp < b[i] and a[i] < b[i]:
            res = (b[i]-a[i]) // (b[(i+1)%n]+b[(i-1)%n])
            answer += res
            b[i] -= res * (b[(i+1)%n]+b[(i-1)%n])
        
    if answer == answer_p:
        break
#    print(a,b,answer)

for i in range(n):
    if a[i] != b[i]:
        print(-1)
        exit()
print(answer)
### BUGGY CODE ###

import fractions
from functools import reduce

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

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

max_gcd = 1
for i in range(n):
  max_gcd = max(max_gcd,gcd(a[:i]+a[i+1:]))
  
print(max_gcd)

### FIXED CODE ###

import sys
import fractions

def solve(N: int, A: "List[int]"):
    A.sort()
    gcd_left = [A[0]] ##iまでのgcd
    for i in range(1,N):
        gcd_left.append(fractions.gcd(A[i],gcd_left[i-1]))
        
    gcd_right = [A[-1]] ##右からiまでのgcd
    for i in range(N-2,-1,-1):
        gcd_right.append(fractions.gcd(A[i],gcd_right[N-2-i]))
    answer = 1

    for i in range(N):
        if i == 0:
            answer = max(answer,gcd_right[N-2])
        elif i == N-1:
            answer = max(answer,gcd_left[N-2])
        else:
            answer = max(answer,fractions.gcd(gcd_left[i-1],gcd_right[N-2-i]))
    print(answer)
    return 


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]"
    solve(N, A)

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

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

aa = a
bb = b

blue_ball = a
red_ball = b

n_bai = n // (a + b)
n_amari = n % (a + b)
balls = ''


while len(balls) < n_amari:
    while aa > 0:
        balls += 'b'
        aa -= 1
    while bb > 0:
        balls += 'r'
        bb -= 1
    aa = a
    bb = b


amari_balls = balls[:n_amari]

ans = (n_bai) * blue_ball + amari_balls.count('b')

print(ans)

### FIXED CODE ###

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

blue_ball = a
red_ball = b

n_bai = n // (a + b)
n_amari = n % (a + b)

balls = []
ans = 0

balls_sum = 0

while balls_sum < n_amari:
    balls.append(a)
    balls.append(b)
    balls_sum = sum(balls)

while n_amari > 0:
    if n_amari > blue_ball:
        ans += blue_ball
    else:
        ans += n_amari
    n_amari = n_amari - blue_ball - red_ball

ans += n_bai * blue_ball

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
def main():
    H, W = map(int , readline().split())
    A = []
    for i in range(H):
        A.append([1 if i == ord('.') else 0 for i in readline()])
    A.append([0 for _ in range(W+1)])

    for j in range(H):
        prev = 0
        start = 0
        for i in range(W+1):
            if A[j][i] > 0:
                if prev == 0:
                    start = i 
                    prev = 1
            else:
                if prev == 1:
                    n = i - start
                    for k in range(start, i):
                        A[j][k] = n
                    prev = 0 
    
    ans = 0
    for i in range(W):
        prev = 0
        start = 0
        for j in range(H+1):
            if A[j][i] > 0:
                if prev == 0:
                    start = j
                    prev = 1
            else:
                if prev == 1:
                    n = j - start - 1
                    for k in range(start, j):
                        A[k][i]+= n
                        ans = max(ans, A[k][i])
                    prev = 0
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
import itertools as it
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, m = map(int, input().split())
d = []
for i in range(m):#h:高さ
    d.append([int(m) for m in input().split()])
e = []
for i in range(m):
    e.append([])
for i in range(m):
    e[i].append(d[i][0] - 1)
    e[i].append(d[i][1] - 1)
    e[i].append(-d[i][2])
#edges = d
#num_v = n
#source = m


#ベルマンフォード
#高々|V|-1回で最安定経路にたどり着くっていうのがなかなか理解できなくて、紙に書きながら理解した。

"""edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]"""
edge = e

"""def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    for i in range(num_v):
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
        if i == num_v - 1:
            d[n - 1] = -inf
            break
    return d"""
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
    return d

print(-shortest_path(edge,n,0)[n - 1])

#print(BellmanFord(e, n, m))

### FIXED CODE ###

n, m = map(int, input().split())
d = []
for i in range(m):#h:高さ
    d.append([int(m) for m in input().split()])
e = []
for i in range(m):
    e.append([])
for i in range(m):
    e[i].append(d[i][0] - 1)
    e[i].append(d[i][1] - 1)
    e[i].append(-d[i][2])
#edges = d
#num_v = n
#source = m


#ベルマンフォード
#高々|V|-1回で最安定経路にたどり着くっていうのがなかなか理解できなくて、紙に書きながら理解した。

"""edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]"""
edge = e

def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    for i in range(num_v):
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
        if i == num_v - 2:
            k = d[-1]
        if i == num_v - 1 and k != d[-1]:
            d[n - 1] = -inf
            break
    return d

print(-shortest_path(edge,n,0)[n - 1])
#print("inf")
#print(BellmanFord(e, n, m))
"""5 5
1 2 2
2 5 4
4 3 1
3 4 2
2 4 1"""
### BUGGY CODE ###

import sys
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

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

### FIXED CODE ###

import sys
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
x = [0]*n
ans = 0
for i in range(n): 
  if a[i]+i < n:
    x[a[i]+i] += 1
  if i-a[i] >= 0:
    ans += x[i-a[i]]
      
print(ans)
### BUGGY CODE ###

n = int(input())

p = 1
for i in range(n):
  p *= (i + 1)

print(p % 1000000007)

### FIXED CODE ###

n = int(input())

mod = 1000000007

p = 1
for i in range(n):
  p = p * (i + 1) % mod

print(p % mod)