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

def check(n, k , a, f, x):
    training_cnt = 0
    for i in range(n):
        t = x // f[i]  #a[i]をこれ以下にしたい。
        d = a[i] - t
        if d > 0:
            training_cnt += d
        if training_cnt > k:
            return False
    else:
        return True

def main():
    N, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    F = sorted([int(i) for i in input().split()], reverse=True)

    if check(N, K, A, F, 0):
        print(0)
        return


    left = 0
    right = 10 ** 12

    while left + 1 < right:
        mid = (left + right) // 2
        if check(N, K, A, F, mid):
            right = mid
        else:
            left = mid

    print(right)

if __name__ == '__main__':
    main()




### FIXED CODE ###

def check(n, k , a, f, x):
    training_cnt = 0
    for i in range(n):
        t = x // f[i]  #a[i]をこれ以下にしたい。
        d = a[i] - t
        if d > 0:
            training_cnt += d
        if training_cnt > k:
            return False
    else:
        return True

def main():
    N, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    F = sorted([int(i) for i in input().split()], reverse=True)

    if check(N, K, A, F, 0):
        print(0)
        return


    left = 0
    right = 10 ** 12

    while left + 1 < right:
        mid = (left + right) // 2
        if check(N, K, A, F, mid):
            right = mid
        else:
            left = mid

    print(right)

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

from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[]
    maxcolor=0
    for i in range(n+1):
        color.append([0]*(n+1))
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u][parent[u]]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[u][t]=col
                color[t][u]=col
                maxcolor=max(maxcolor,col)
                Q.append(t)
                col+=1
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[a][b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)


### FIXED CODE ###

from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        #nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)
### BUGGY CODE ###

#!/usr/bin/env python3
# coding:utf-8

def main():
    stdIn1, stdIn2 = map(int, input().split())
    stdOut = solve(stdIn1, stdIn2)
    print(stdOut)


"""
方針
x,y,zそれぞれを3重ループで0からkまで回す
(O(N^3)だが、k<=2500なので気にならない)
x+y+zが等しければパターンを1追加

TLEになったので、もう少し節約するパターンを考える必要あり
ひとまずx,x+y,x+y+zがsより大きなった場合はbreakさせてループを抜ける処理にしてみる

"""


def solve(k, s):
    pattern = 0
    for x in range(k+1):
        if x > s:
            break
        for y in range(k+1):
            if x + y > s:
                break
            for z in range(k+1):
                if x + y + z > s:
                    break
                if x+y+z == s:
                    pattern += 1

    return pattern


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# coding:utf-8

def main():
    stdIn1, stdIn2 = map(int, input().split())
    stdOut = solve(stdIn1, stdIn2)
    print(stdOut)


"""
方針
x,y,zそれぞれを3重ループで0からkまで回す
(O(N^3)だが、k<=2500なので気にならない)
x+y+zが等しければパターンを1追加

TLEになったので、もう少し節約するパターンを考える必要あり
ひとまずx,x+y,x+y+zがsより大きなった場合はbreakさせてループを抜ける処理にしてみる
まだTLEになるので、もう少し考える
実はzはループする必要はなく z = s - (x + y) <= k であれば +1, > k であれば continueでよい
これでO(N^2)に計算量を抑えられる

"""


def solve(k, s):
    pattern = 0
    for x in range(k+1):
        if x > s:
            break
        for y in range(k+1):
            if x + y > s:
                break
            z = s - x - y
            if z <= k:
                pattern += 1

    return pattern


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

X,K,D = map(int,input().split())
X = abs(X)
#0またがない
if X > K*D:
    ans = X - K*D
#0またぐ
else:
    while X >= 0 :
        X = X - D
        K -= 1
    if K % 2 == 0:
        ans = abs(X)
    if K % 2 != 0:
        ans = X+D

print(ans)

### FIXED CODE ###

X,K,D = map(int,input().split())
X = abs(X)
#0またがない
if X > K*D:
    ans = X - K*D
#0またぐ
else:
    time = X//D + 1
    K = K - time
    X = X - time*D
    if K % 2 == 0:
        ans = abs(X)
    if K % 2 != 0:
        ans = X+D

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

def walk(current_childs):
    new_childs = [0 for i in range(len(S))]
    for s in range(len(S)):
        if(S[s] == "R"):
            new_childs[s+1] += current_childs[s]
        elif(S[s] == "L"):
            new_childs[s-1] += current_childs[s]
    return new_childs

S = input().strip()

childs_list = [1 for i in range(len(S))]
prev_childs_list = childs_list
childs_list = walk(childs_list)
loop_index = 0
while(True):
    loop_index += 1
    new_childs_list = walk(childs_list)
    if(new_childs_list == prev_childs_list):
        break
    prev_childs_list = childs_list
    childs_list = new_childs_list
if(loop_index % 2 == 0):
    print(" ".join(map(str, childs_list)))
else:
    print(" ".join(map(str, prev_childs_list)))

### FIXED CODE ###

import collections

S = input().strip()

valley_collections = collections.Counter()
saved_index_set = set()
last_saved_index = -1
for s in range(len(S)):
    if(S[s] == "L"):
        if(len(saved_index_set) > 0):
            for i in saved_index_set:
                valley_collections[i] = s - 1
            valley_collections[s] = s - 1
            last_saved_index = s - 1        
            saved_index_set.clear()
        else:
            valley_collections[s] = last_saved_index
    else:
        saved_index_set.add(s)

ans = [0 for i in range(len(S))]
for s in range(len(S)):
    if((valley_collections[s] - s) % 2 == 0):
        ans[valley_collections[s]] += 1
    else:
        ans[valley_collections[s] + 1] += 1
print(" ".join(map(str, ans)))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(1, n + 1):
    now = a[i - 1]
    for j in range(i + now, n):
        if a[j] + now == (j+1) - i:
            ans += 1

print(ans)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
ans = 0
R = {}
L = {}
for i in range(n):
    r = i + a[i]
    l = max(i - a[i], 0)
    if r in R:
        R[r] += 1
    else:
        R[r] = 1
    if l in L:
        L[l] += 1
    else:
        L[l] = 1

for k, v in R.items():
    if k in L:
        ans += v * L[k]

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


def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    #A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

[N, K] = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

sum_list = []
for i in range(len(P)-(K-1)):
    sum_list.append(sum(P[i: i+K]))

#print(sum_list)
max_index = sum_list.index(max(sum_list))
#print(max_index)

# 隣接したK個のリスト
kk = P[max_index: max_index+K]

# kの期待値を計算
max_kk = max(kk)
dp = [0]
for i in range(1, max_kk+1):
    dp.append(dp[i-1] + i)
#print(dp)

ans = 0
for k in kk:
    ans += dp[k]/k

print(ans)

### FIXED CODE ###

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

#def f(x):
#    if x == 1:
#        return 1
#    else:
#        return f(x-1) + x

[N, K] = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

max_index = 0
now_sum = sum(P[:K])
max_sum = now_sum
for i in range(1, len(P)-(K-1)):
    now_sum -= P[i-1]
    now_sum += P[i+K-1]
    #sum_P = sum(P[i:i+K])
    if now_sum > max_sum:
        max_sum = now_sum
        max_index = i

#print(max_sum)
#print(max_index)

# 隣接したK個のリスト
kk = P[max_index:max_index+K]

# kの期待値を計算
max_kk = max(kk)
dp = [0]
for i in range(1, max_kk+1):
    dp.append(dp[i-1] + i)
#print(dp)

ans = 0
for k in kk:
    ans += dp[k]/k

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

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp = [[[-10**9,-10**9] for _ in range(n//2+2)] for _ in range(n+1)]
	dp[1][1][1]=a[1]
	for i in range(0,n+1):
		dp[i][0]=[0,0]
	for i in range(1,n+1):
		if i-1 >= 3:
			dp[i][(i-1)//2][0]=max(dp[i-1][(i-1)//2][0], dp[i-1][(i-1)//2][1])
			dp[i][(i-1)//2][1]=max(dp[i-1][(i-1)//2-1][0]+a[i], dp[i-2][(i-1)//2-1][0]+a[i])
		if i >= 2:
			dp[i][i//2][0]=max(dp[i-1][i//2][0], dp[i-1][i//2][1])
			dp[i][i//2][1]=max(dp[i-1][i//2-1][0]+a[i], dp[i-2][i//2-1][0]+a[i])
		if i >= 2:
			dp[i][(i+1)//2][1]=max(dp[i-1][(i+1)//2-1][0]+a[i], dp[i-2][(i+1)//2-1][0]+a[i])
	print(max(dp[n][n//2]))
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp_t = defaultdict(lambda: -10**18)
	dp_f =  defaultdict(lambda: -10**18)
	dp_f[(0,0)]=0
	for i in range(1,n+1):
		dp_f[(i,(i-1)//2)]=max(dp_f[(i-1,(i-1)//2)], dp_t[(i-1,(i-1)//2)])
		dp_t[(i,(i-1)//2)]=dp_f[(i-1,(i-1)//2-1)]+a[i]
		dp_f[(i,(i-1)//2+1)]=max(dp_f[(i-1,(i-1)//2+1)], dp_t[(i-1,(i-1)//2+1)])
		dp_t[(i,(i-1)//2+1)]=dp_f[(i-1,(i-1)//2)]+a[i]
	print(max(dp_t[(n,n//2)],dp_f[(n,n//2)]))
if __name__ == '__main__':
	main()
### BUGGY CODE ###

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

dp = [0] * (N + 1)
dp[0] = 1

for i in range(-1, N - 1):
    if i + 2 in A:
        dp[i + 2] = 0
    elif i + 2 == 1:
        dp[i + 2] = dp[i + 1]
    else:
        dp[i + 2] = (dp[i + 1] + dp[i]) % (10 ** 9 + 7)
        
print(dp[-1])

### FIXED CODE ###

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

B = [-1] + A + [N + 1]
B = [B[i + 1] - B[i] - 2 for i in range(M + 1)]

total = max(B)
dp = [1, 1] + [0] * (total - 1)
for i in range(total - 1):
    dp[i + 2] = (dp[i + 1] + dp[i]) % (10 ** 9 + 7)
        
ans = 1
for i in range(M + 1):
    ans *= dp[B[i]]
    ans %= 10 ** 9 + 7
print(ans if -1 not in B[1:] else 0)
### BUGGY CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        if x % a[i] != 0:
            x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = [lcm_num//ai for ai in a]

print(sum(ans)%div)


### FIXED CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = [lcm_num//ai for ai in a]

print(sum(ans)%div)
### BUGGY CODE ###

import sys

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

if 0 in A :
    print(0)
    sys.exit()

for i in range(N):
    a = a*A[i]
    
if a > 10**18 :
    print(-1)    
    sys.exit()

else : print(a)



### FIXED CODE ###

import sys

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

if 0 in A :
    print(0)
    sys.exit()

for i in range(N):
    a = a*A[i]
    if a > 10**18 :
        print(-1)    
        sys.exit()

else : print(a)
### BUGGY CODE ###

import math
N = int(input())
if N % 2 == 1:
  print(0)
else:
  print(sum([int(math.log10(i)) for i in range(1, N + 1) if i % 10 == 0]))

### FIXED CODE ###

L = [10, 50, 250, 1250, 6250, 31250, 156250, 781250, 3906250, 19531250, 97656250, \
     488281250, 2441406250, 12207031250, 61035156250, 305175781250, 1525878906250, \
     7629394531250, 38146972656250, 190734863281250, 953674316406250, \
     4768371582031250, 23841857910156250, 119209289550781250, 596046447753906250]
N = int(input())
A = 0
if N % 2 == 0:
  for i in L:
    A += N // i
print(A)
### BUGGY CODE ###

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

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(2 ** N):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)


### FIXED CODE ###

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

p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(p2):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
 
print(ans if ans != 10 ** 9 else -1)
### BUGGY CODE ###

a,b,c,d,e,f=map(int, input().split())
 
W=[100*a*x + 100*b*y for x in range(0,31) for y in range(0,31) if 0<(100*a*x+100*b*y)<=f]
S=[c*x+d*y for x in range(0,3001) for y in range(0,3001) if 0<(c*x+d*y)<=f]
 
dense = 0
sugar = 0
mass = 100*a
for w in W:
    for s in S:
        if (w+s<=f and s<=(w*e/100) and dense*(s+w)<s):
            dense=s/(s+w)
            sugar=s
            mass=s+w
print(mass,sugar)

### FIXED CODE ###

a,b,c,d,e,f=map(int, input().split())
 
W=[100*a*x + 100*b*y for x in range(0,31) for y in range(0,31) if 0<(100*a*x+100*b*y)<=f]
S=[c*x+d*y for x in range(0,3001) for y in range(0,3001) if 0<(c*x+d*y)<=f]
 
dense = 0
sugar = 0
mass = 100*a
for w in W:
    for s in S:
        if (w+s<=f and s<=(w*e/100) and dense*(s+w)<s):
            dense=s/(s+w)
            sugar=s
            mass=s+w
print(mass,sugar)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        if (0 <= s - x - y) and (s - x - y <= k):
                ans += 1
print(ans)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

    # 各町の座標をタプル(i, x, y)に入れて配列に格納
    xs = []
    ys = []
    for i in range(N):
        x, y = map(int, input().split())
        bisect.insort_left(xs, (x, i))
        bisect.insort_left(ys, (y, i))

    # 使う可能性のある辺のみを取り出す
    edges = []
    for i in range(1, N):
        bisect.insort_left(edges, (xs[i][0] - xs[i-1][0], xs[i-1][1], xs[i][1]))
        bisect.insort_left(edges, (ys[i][0] - ys[i-1][0], ys[i-1][1], ys[i][1]))

    # クラスカル法
    ans = 0
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

    # 各町の座標をタプル(i, x, y)に入れて配列に格納
    xy = []
    for i in range(N):
        x, y = map(int, input().split())
        xy.append((i, x, y))
    
    # 使う可能性のある辺のみを取り出す
    edges = []
    xy = sorted(xy, key=lambda x: x[1])# x座標昇順
    # print("x:", xy)
    for i in range(1, N):
        edges.append((xy[i][1] - xy[i-1][1], xy[i-1][0], xy[i][0]))
    xy = sorted(xy, key=lambda x: x[2])# y座標昇順
    # print("y:", xy)
    for i in range(1, N):
        edges.append((xy[i][2] - xy[i-1][2], xy[i-1][0], xy[i][0]))
    
    ans = 0
    edges = sorted(edges)
    # print(edges)
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)




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

import sys


def prime(x):
    for i in p_list:
        if x % i == 0:
            return 0
    return 1


if __name__ == "__main__":
    a = 10000
    i = 2
    p_list = []
    while i < a:
        if prime(i):
            p_list.append(i)
        i += 1
    print(p_list)

    for i in sys.stdin:
        n = int(i)
        while 1:
            if n not in p_list:
                n -= 1
            else:
                print(p_list.index(n) + 1)

### FIXED CODE ###

import sys

f = [1, 0, 0, 0, 1, 0] * (1000000 // 6 + 1)
f = [0, 0, 1, 1] + f[3:-2]

i = 5
while i < 1000:
    if f[i] == 1:
        j = i * i
        while j <= 1000000:
            f[j] = 0
            j += i + i
    i += 2

for n in sys.stdin:
    i = int(n)
    print(sum(f[:i + 1]))
### BUGGY CODE ###

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

result = 0
for i in range(N):
    a = A[i]
    b = a + i
    for j in range(1, N - a - i):
        if j == A[j + b]:
            result += 1
print(result)


### FIXED CODE ###

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

c1 = {}
c2 = {}

for i in range(N):
    c1.setdefault(i + A[i], 0)
    c1[i + A[i]] += 1
    c2.setdefault(i - A[i], 0)
    c2[i - A[i]] += 1

result = 0
for k in set(c1).intersection(c2):
    result += c1[k] * c2[k]
print(result)