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

import sys
sys.setrecursionlimit(200010)

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

G = [[] for k in range(N+1)]

for k in range(N-1):
    a, b = map(int,input().split())
    G[a].append(b)

kyori = [0 for k in range(N+1)]

for k in range(Q):
    p, x = map(int,input().split())
    kyori[p] -= x

def dfs(now, dist):
    for tsugi in G[now]:
        if kyori[tsugi] <= 0:
            kyori[tsugi] = -kyori[tsugi]
            kyori[tsugi] += dist
            dfs(tsugi, kyori[tsugi])
kyori[1] = -kyori[1]
dfs(1,kyori[1])

print(*kyori[1:], sep = " ")


### FIXED CODE ###

import sys
sys.setrecursionlimit(200010)

def main():
    input = sys.stdin.readline
    N, Q = map(int,input().split())
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
    kyori = [0 for k in range(N+1)]
    for k in range(Q):
        p, x = map(int,input().split())
        kyori[p] -= x
    def dfs(now, dist):
        for tsugi in G[now]:
            if kyori[tsugi] <= 0:
                kyori[tsugi] = -kyori[tsugi]
                kyori[tsugi] += dist
                dfs(tsugi, kyori[tsugi])
    kyori[1] = -kyori[1]
    dfs(1,kyori[1])
    print(*kyori[1:], sep = " ")

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

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
S = input()[::-1]

MOD = 2019
tmp = [0]*MOD
tmp[0] += 1
tens = 1
num = 0
for s in S:
    num += int(s) * tens
    key = num % MOD
    tmp[key] += 1
    tens *= 10

ans = 0
for i in tmp:
    ans += i*(i-1)//2

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
S = input()[::-1]

MOD = 2019
tmp = [0]*MOD
tmp[0] += 1
tens = 1
num = 0
for s in S:
    num += int(s) * tens
    num = num % MOD
    tmp[num] += 1
    tens *= 10
    tens %= MOD

ans = 0
for i in tmp:
    ans += i*(i-1)//2

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))
### BUGGY CODE ###

k = int(input())
 
qu = list(range(1,10))
 
cnt = 0
while( cnt < k ):
  out = qu.pop(0)
  r = out%10
  y = 10*out+r
  if( r != 0 ):
    qu.append(y-1)
  qu.append(y)
  
  if( r!=9):
    qu.append(y+1)
  cnt+=1
    
print(out)

### FIXED CODE ###

k = int(input())
 
qu = list(range(1,10))
 
if (k <= 9):
  print(k)
else:
  cnt = 9
  while( cnt < k ):
    out = qu.pop(0)
    r = out%10
    y = 10*out+r
    if( r != 0 ):
      qu.append(y-1)
      cnt += 1
      if( cnt == k ):
        out = y-1
        break
    qu.append(y)
    cnt += 1
    if( cnt == k ):
      out = y
      break

    
    if( r!=9):
      qu.append(y+1)
      cnt+=1
      if( cnt == k ):
        out = y+1
        break
      

  print(out)
### BUGGY CODE ###

from queue import Queue
n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
def bfs():
    queue = Queue()
    queue.put((1, 0))
    visited = [False]*(n+1)
    while not queue.empty():
        u, step = queue.get()
        if u == n and step == 2:
            print ("POSSIBLE")
            return
        for a in adj[u]:
            if step + 1 <= 2:
                queue.put((a, step+1))
    print ("IMPOSSIBLE")
    return
bfs()

### FIXED CODE ###

from queue import Queue
n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
def bfs():
    queue = Queue()
    queue.put(1)
    distance = [10**6]*(n+1)
    distance[1] = 0
    while not queue.empty():
        u = queue.get()
        if u == n and distance[u] == 2:
            print ("POSSIBLE")
            return
        for a in adj[u]:
            if distance[u] + 1 <= 2 and distance[a] > distance[u] + 1:
                distance[a] = distance[u] + 1
                queue.put(a)
    print ("IMPOSSIBLE")
    return
bfs()
### BUGGY CODE ###

import sys

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1
hmaxindex = [i for i in range(H) if hcnt[i] == hmax]#[0]
wmaxindex = [i for i in range(W) if wcnt[i] == wmax]#[0,1,2]
#crosspoint has not bomb

for i in hmaxindex:
    for j in wmaxindex:
        if (i,j) not in bomb:
            print(hmax + wmax)
            sys.exit()
        else:
            continue
#all crosspoint has bomb
print(hmax + wmax - 1)


### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

N,M=map(int,input().split())
v=[]
x=[]
y=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        x.append(b)
    if b==N:
        y.append(a)
for i in x:
    if i in y:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M=map(int,input().split())
x=[0]*(N+1)
y=[0]*(N+1)
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        x[b]=1
    if b==N:
        y[a]=1
for i in range(N+1):
    if x[i]==1 and y[i]==1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

def exam(L, R):
    min = 2019
    if L-R > 2019:
        return 0
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            modval = i*j % 2019
            if modval < min:
                min = modval
    return min


L, R = map(int, input().split())
print(exam(L, R))


### FIXED CODE ###

def exam(L, R):
    min = 2019
    if L-R > 2019:
        return 0
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            modval = i*j % 2019
            if modval < min:
                min = modval
                if min == 0:
                    return 0
    return min


L, R = map(int, input().split())
print(exam(L, R))
### BUGGY CODE ###

N =int(input())
L = list(map(int,input().split()))
A=1
for i in range(N):
    if 0 in L:
        print(0)
        break
    A = A * L[i]
    if i == N-1 and A <= 10**18:
        print(A)
    elif A > 10**18:
        break
if A > 10**18:
    print(-1)

### FIXED CODE ###

N = int(input())
Alist = list(map(int,input().split()))
Answer = 1
if 0 in Alist:
    Answer = 0
for i in range(N):
    Answer *= Alist[i]
    if Answer > 10**18:
        Answer = -1
        break
print(Answer)
### BUGGY CODE ###

def k_sub():
    s=input()
    k=int(input())
    a=[]
    for i in range(1,len(s)+1):
        for j in range(len(s)+1-i):
            a.append(s[j:j+i])
    a=sorted(set(a))
    #print(a)
    print(a[k-1])

if __name__=='__main__':
    k_sub()

### FIXED CODE ###

s=input()
k=int(input())

a=sorted({s[i:i+j+1] for i in range(len(s)) for j in range(k)})[k-1]
print(a)
### BUGGY CODE ###

import heapq

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

A = sorted(A)
F = sorted(F, reverse = True)

AF = [[A[i]*F[i]*(-1), F[i]] for i in range(N)]
heapq.heapify(AF)
for _ in range(K):
	t,f = heapq.heappop(AF)
	heapq.heappush(AF,[min(0,t+f), f])

ans, f = heapq.heappop(AF)
print(ans*(-1))

### FIXED CODE ###



N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse = True)
F.sort()

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))
### BUGGY CODE ###

n = int(input())
a = list()
for i in range(n):
    a.append(int(input()))
for i in range(n):
    b = a[:]
    b.pop(i)
    print(max(b))

### FIXED CODE ###

n = int(input())
a = list()
for i in range(n):
    x = input()
    a.append(int(x))
second = sorted(a)[-2]
m = max(a)
for i in range(n):
    if m == a[i]:
        print(second)
    else:
        print(m)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            s[i][j] = min(i,N-1-i,j,N-1-j)

    r = [[1] * N for _ in range(N)]

    ans = 0
    q = collections.deque()
    for p in P:
        x = (p-1)//N
        y = (p-1) % N
        ans += s[x][y]
        r[x][y] = 0
        q.append((x,y))
        while q:
            a,b = q.pop()
            nc = s[a][b] + r[a][b]
            for da,db in ((1,0),(0,1),(-1,0),(0,-1)):
                na = a + da; nb = b + db
                if 0 < na < N-1 and 0 < nb < N-1:
                    if s[na][nb] <= nc: continue
                    s[na][nb] = nc
                    q.append((na,nb))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

#入力
K, S = map(int, input().split())

#問題文よりX, Y, Zの最大値はKである
X = range(K+1)
Y = range(K+1)
Z = range(K+1)

#フラグ設定
flag = 0

#全探索
for x in X:
    for y in Y:
        for z in Z:
            
            #条件
            if x+y+z==S:
                flag += 1

#出力
print(flag)

### FIXED CODE ###

#入力
K, S = map(int, input().split())

#問題文よりX, Y, Zの最大値はKであるため、各値の最大値はKである
X = range(K+1)
Y = range(K+1)

#フラグ設定
flag = 0

#全探索
for x in X:
    for y in Y:
        #条件に合うzの値を算出
        z = S - x - y
        if z<=K and z>=0:  #上で求めたzの値に問題文からFilterを掛ける
            flag += 1

#出力
print(flag)
### BUGGY CODE ###

import itertools
N,K,*p = map(int,open(0).read().split())
print(min(map(lambda x: sum(x),itertools.combinations(p,K))))

### FIXED CODE ###

N,K,*p = map(int,open(0).read().split())
p.sort()
print(sum(p[:K]))
### BUGGY CODE ###

n = int(input())
listA = list(map(int, input().split()))
listB=[]

index=0
while index < n:
    a = listA[index]
    listB.append(a)
    listB.reverse()
    index+=1

print(" ".join(list(map(str, listB))))

### FIXED CODE ###

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

stA=""
if n%2 == 0:
    index = len(listA)-1
    while index > 0:
        if index== len(listA)-1:
            stA +=str(listA[index])
        else:
            stA+=" "+str(listA[index])
        index-=2
    index = 0
    while index < len(listA)-1:
        stA+=" "+str(listA[index])
        index+=2
else:
    index = len(listA)-1
    while index > -1:
        if index == len(listA)-1:
            stA += str(listA[index])
        else:
            stA += " "+str(listA[index])
        index -= 2
    index = 1
    while index < len(listA)-1:
        stA += " "+str(listA[index])
        index += 2
        
print(stA)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
freq={}
for i in range(n):
	freq[l[i]]=0
for i in range(n):
	freq[l[i]]+=1
t=int(input())
for i in range(t):
	a,b=map(int,input().split())
	if(a not in freq.keys()):
		sm=0
		for x, y in freq.items():
			sm+=(x*y)
		print(sm)
	else:
		if(b not in freq.keys()):
			freq[b]=0
		freq[b]+=freq[a]
		freq[a]=0
		sm=0
		for x, y in freq.items():
			sm+=(x*y)
		print(sm)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
freq={}
for i in range(n):
	freq[l[i]]=0
for i in range(n):
	freq[l[i]]+=1
t=int(input())
sm=sum(l)
for i in range(t):
	a,b=map(int,input().split())
	if(a not in freq.keys()):
		print(sm)
	else:
		if(b not in freq.keys()):
			freq[b]=0
		#diff=abs(freq[b]-freq[a])
		sm=sm-a*freq[a]+b*freq[a]
		freq[b]+=freq[a]
		freq[a]=0
		print(sm)
### BUGGY CODE ###

n, k = map(int, input().split())
hn = list(map(int, input().split()))
dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(0, n):
    for j in range(1, min(k+1, n-i)):
        dp[i+j] = min(dp[i+j], dp[i] + abs(hn[i+j]-hn[i]))
print(dp[-1])


### FIXED CODE ###

n, k = map(int, input().split())
hn = list(map(int, input().split()))
dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(0, n):
    for j in range(1, min(k+1, n-i)):
        dp[i+j] = min(dp[i+j], dp[i] + abs(hn[i+j]-hn[i]))
print(dp[-1])
### BUGGY CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited_black = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append([h,w])

    for h, w in blacks:
        if not visited_black[h][w]:
            visited_white = [[False] * W for _ in range(H)]
            Q = deque([[h,w]])
            white = 0
            black = 1
            visited_black[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if now == '#':
                        if S[nh][nw] == '.' and (not visited_white[nh][nw]):
                            white += 1
                            visited_white[nh][nw] = True
                            Q.append([nh,nw])
                    else:
                        if S[nh][nw] == '#' and (not visited_black[nh][nw]):
                            black += 1
                            visited_black[nh][nw] = True
                            Q.append([nh,nw])
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append((h,w))

    for h, w in blacks:
        if not visited[h][w]:
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited[h][w] = True
            while Q:
                i, j = Q.pop()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if 0 <= nh < H and 0 <= nw < W:
                        if not visited[nh][nw]:
                            if now != S[nh][nw]:
                                visited[nh][nw] = True
                                Q.append((nh,nw))
                                if S[nh][nw] == '.':
                                    white += 1
                                else:
                                    black += 1
            ans += white * black

    print(ans)


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

a = input().rstrip().split(" ")
K = int(a[0])
A = int(a[1])
B = int(a[2])

bis = 1
coin = 0

if B - A > 1:
    for i in range(K):
        if coin > 0:
            bis += B
            coin -= 1
        elif bis >= A and K - i > 1:
            bis -= A
            coin += 1
        else:
            bis += 1
else:
    for i in range(K):
        bis += 1

print(bis)

### FIXED CODE ###

a = input().rstrip().split(" ")
K = int(a[0])
A = int(a[1])
B = int(a[2])

bis = 1

if B - A > 1:
    if K >= A + 1:
        # bis = (K - (A - 1)) // 2 * (B - A) + A
        koukan = (K - (A - 1)) // 2
        koukan_turn = koukan * 2
        nokori_turn = K - koukan_turn
        bis += koukan * (B - A) + nokori_turn
    else:
        bis += K
else:
    bis += K
    
print(bis)
### BUGGY CODE ###

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table
  
n = int(input())
ans = 0


for c in range(1,n):
    ab = n - c
    ans += num_divisors_table(ab)[-1]
print(ans)


### FIXED CODE ###

import math
n = int(input())
ans = 0

for a in range(1, n):
    ans += math.floor((n-1)/a)
print(ans)
### BUGGY CODE ###

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

L = []
cnt = 1
for i in range(N-K+1):
    for j in range(K):
        cnt = cnt*point[j+i]
    L.append(cnt)
    cnt = 1

for k in range(N-K):
    if L[k] > L[k+1]:
        print("No")
    elif L[k] == L[k+1]:
        print("No")
    else:
        print("Yes")



### FIXED CODE ###

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

for i in range(k,n):
    if a[i] > a[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import collections
n = int(input())
num_list = list(map(int, input().split()))
cnt_list = [0] * n

for k in range(n):
    cnt_list[k] = num_list.count(num_list[k]) - 1

for k in range(n):
    ans = sum(cnt_list)//2 - cnt_list[k]
    print(ans)

### FIXED CODE ###

import collections
n = int(input())
num_list = list(map(int, input().split()))
all = 0

c = collections.Counter(num_list)

for i in c:
    all += c[i]*(c[i]-1)//2

for k in range(n):
    print(all - c[num_list[k]] + 1)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
P = [int(sys.stdin.readline()) for _ in range(N)]
Q = [P.index(i) for i in range(1, N + 1)]
ans = 0
prv_q = 0
now = 0
for i in range(N):
    if prv_q > Q[i]:
        now = 0
    now += 1
    prv_q = Q[i]
    ans = max(ans, now)
print(N - ans)


### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
P = {int(sys.stdin.readline()): i for i in range(N)}
Q = [P[i] for i in range(1, N + 1)]

ans = 0
prv_q = 0
now = 0
for i in range(N):
    if prv_q > Q[i]:
        now = 0
    now += 1
    prv_q = Q[i]
    ans = max(ans, now)
print(N - ans)
### BUGGY CODE ###

n, k = map(int,input().split())
l = list(map(int,input().split()))
#print(l)

x = 0
y = 0
for i in range(n-k+1):
    a = sum(l[i:i+k])
    if x < a:
        x = a
        y = i
#print(x,y)

z = 0
#for j in range(y,y+k):
#    z += (l[j]+1)/2

print((sum(l[y:y+k]) + k)/2)

### FIXED CODE ###

from itertools import accumulate

n, k = map(int,input().split())
l = list(map(int,input().split()))
#print(l)

p = [0] + list(accumulate(l))

#print(p)

q = []
for i in range(n-k+1):
    q.append((p[i+k] - p[i] + k)/2)

print(max(q))
### BUGGY CODE ###

N =int(input())
A = list(map(int,input().split()))
x=0
y=0
ans =0
while x <N:
    y =x+A[x]
    while y <N:
        t = A[x]+A[y]
        if t == y-x:
            ans +=1
        y+=1
    x+=1
print(ans)

### FIXED CODE ###

N =int(input())
A = list(map(int,input().split()))
d ={}
r ={}
ans =0
for x in range(N):
    d[x] =0
    r[x] =0
for x in range(N):
    dt = A[x]+x
    rt = x-A[x]
    if dt<N:
        d[dt] +=1
    if rt >-1:
        r[rt] +=1
for x in range(N):
    if d[x] !=0 and r[x]!=0:
        ans = ans + d[x]*r[x]
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []

# cnt_sum = 0
# min_num = BC[0][1]
# for i in range(M):
#     cnt = BC[i][0]
#     for j in range(N):
#         if cnt_sum <= N:
#             L.append(BC[i][1])
#             cnt_sum += 1
#             cnt -= 1
#             if BC[i][1] < min_num:
#                 min_num = BC[i][1]
#         else:
#             if BC[i][1] < min_num:
#                 break
#             if L[j] < BC[i][1]:
#                 L[j] = BC[i][1]
#                 cnt -= 1
#         if cnt <= 0:
#             break
len_L = 0
for i in range(M):
    # for j in range(BC[i][0]):
    #     L.append(BC[i][1])
    L.extend([BC[i][1] for j in range(BC[i][0])])
    len_L += BC[i][0]
L.sort(reverse=True)
A.sort()
# ans = sum(A)
ans = 0
flag = True
for k in range(N):
    if k <= len_L-1:
        if flag and L[k] > A[k]:
            ans += L[k]
        else:
            flag = False
            ans += A[k]
    else:
        ans += A[k]
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
# ans = sum(A)
ans = 0
# flag = False
cnt = 0
# for k in range(N):
#     if k <= len_L-1:
#         if flag and L[k] > A[k]:
#             ans += L[k]
#         else:
#             flag = False
#             ans += A[k]
#     else:
#         ans += A[k]
for i in range(M):
    for j in range(BC[i][0]):
        if cnt < N and A[cnt] < BC[i][1]:
            ans += BC[i][1]
            cnt += 1
        else:
            break
    else:
        continue
    break

if cnt < N:
    ans += sum(A[cnt::])

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

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

ans = [0 for i in range(1000)]
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            s = S[i] + S[j] + S[k]
            ans[int(s)] = 1
print(sum(ans))

### FIXED CODE ###

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

def judge(A,B,C):
    s = S
    a = s.find(A)
    if a < 0:
        return False

    s = s[a+1:]
    b = s.find(B)
    if b < 0:
        return False

    s = s[b+1:]
    c = s.find(C)
    if c < 0:
        return False
    return True

l = '0123456789'
print(sum([int(bool(judge(a,b,c))) for a in l for b in l for c in l]))