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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
ans = 0
B = N
for z in range(2, int(N**(1/2))+1):
    if B == 1:
        break
    if B < z:
        break
    cnt = len(factorization(z))
    if cnt == 1 and B % z == 0:
        B = B // z
        #print(z)
        ans += 1

if(N == 1):
    print(0)
elif(N != 1 and ans == 0):
    print(1)
else:
    print(ans)


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
ans = 0

A = factorization(N)

for x in A:
    e = x[1]
    for y in range(1,N):
        if e >= y:
            e -= y
            ans += 1
        else:
            break

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

K = int(input())
S = input()
N = len(S)

MOD = 10 ** 9 + 7

# 逆元を利用してcomb(nCk)をO(1)計算
# https://qiita.com/ophhdn/items/5622ac22cce8fc9432bf
n = N + K + 3
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % MOD

inv[n] = pow(fac[n], MOD-2, MOD)
for j in range(n - 1, -1, -1):
    inv[j] = (inv[j + 1] * (j + 1)) % MOD

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return (fac[n] * inv[n - r] * inv[r]) % MOD

ans = 0
for i in range(K + 1):
  p = comb(N + K - i - 1, N - 1) * pow(26, i, MOD) * pow(25, K - i, MOD) % MOD
  ans += p
  ans %= MOD
  
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
N = len(S)

MOD = 10 ** 9 + 7

# 逆元を利用してcomb(nCk)をO(1)計算
# https://qiita.com/ophhdn/items/5622ac22cce8fc9432bf
n = N + K + 3
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % MOD

inv[n] = pow(fac[n], MOD-2, MOD)
for j in range(n - 1, -1, -1):
    inv[j] = (inv[j + 1] * (j + 1)) % MOD

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return (fac[n] * inv[n - r] * inv[r]) % MOD

ans = 0
for i in range(K + 1):
  p = comb(N + K - i - 1, N - 1) * pow(26, i, MOD) * pow(25, K - i, MOD) % MOD
  ans += p
  ans %= MOD
  
print(ans)
### BUGGY CODE ###

a,b = map(int, input().split())
count = 0
for i in range(a + 1):
  for j in range(a + 1):
    for k in range(a + 1):
      if i + j + k == b:
        count += 1
print(count)

### FIXED CODE ###

a,b = map(int, input().split())
count = 0
k = 0
for i in range(a + 1):
  for j in range(a + 1):
    k = b - (i + j)
    if 0 <= k and k <= a:
      count += 1
print(count)
### BUGGY CODE ###

from collections import *
from operator import mul

n = int(input())
A = list(map(int, input().split()))
q = int(input())


A_dic = Counter(A)

for _ in range(q):
    b, c = map(int, input().split())
    tmp = A_dic[b]
    A_dic[c] += tmp
    A_dic[b] = 0
    v, c = zip(*A_dic.most_common())
    ans = map(mul, v, c)
    print(sum(ans))

### FIXED CODE ###

from collections import *
from operator import mul

n = int(input())
A = list(map(int, input().split()))
q = int(input())


A_dic = Counter(A)
A_sum = sum(A)

for _ in range(q):
    b, c = map(int, input().split())
    tmp = A_dic[b]
    A_dic[c] += tmp
    A_dic[b] = 0
    A_sum += tmp*(c - b)
    print(A_sum)
### BUGGY CODE ###

n = int(input())
s = [sorted(input()) for _ in range(n)]
ans = 0
for i in range(n):
  for j in range(i+1, n):
    if s[i] == s[j]: ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
s = {}
for _ in range(N):
  a = "".join(sorted(input()))
  if a not in s:
    s[a] = 0
  else: s[a] += 1

import math
ans = 0
for v in s.values():
  if v < 2: ans += v
  if v > 1: ans += v*(v+1)//2
print(ans)
### BUGGY CODE ###

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

def compare(item):
  return item[3]

newXL = sorted([[x, l, x-l, x+l] for x, l in XL], key=compare)

memo = [0]*N
memo[0] = 1

for i in range(N):
  flag = True
  for j in range(N):
    if memo[j] == 1:
      if newXL[i][2] < newXL[j][3]:
        flag = False
  if flag:
    memo[i] = 1

print(sum(memo))

### FIXED CODE ###

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

newXL = sorted([[x-l, x+l] for x, l in XL], key=lambda x:x[1])

previous = 0
total = 1

for i in range(1, N):
  if newXL[i][0] < newXL[previous][1]:
    pass
  else:
    previous = i
    total += 1
    
print(total)
### BUGGY CODE ###

import math

def f(l):
    mx=max(l)
    flg=True
    for i in range(len(l)):
        if (mx==l[i] and flg==True):
            flg=False
            l[i]-=50
            l[i]=max(0,l[i])
        else:
            l[i]+=1
    return l


k=int(input())
N=50
a=math.ceil((k+1)/N)
a=int(a)
l=[a+i for i in range(50)]
mod=N-k%N
for i in range(mod):
    l=f(l)
print(50)
for i in range(50):
    print(str(l[i])+" ",end="")
print("")
ret=0
while (max(l)>=50):
    l=f(l)
    ret+=1
##if (ret!=k):
##    print(k)
    #assert(ret==k and "{}".format(k))

### FIXED CODE ###

import math

def f(l):
    mx=max(l)
    flg=True
    for i in range(len(l)):
        if (mx==l[i] and flg==True):
            flg=False
            l[i]-=50
            l[i]=max(0,l[i])
        else:
            l[i]+=1
    return l


def solve(k):
    #k=int(input())
    N=50
    a=k//N+1
    if (k%N==0) :
        a-=1
    l=[a+i for i in range(50)]
    mod=(N-(k%N))%N
    for i in range(mod):
        l=f(l)
    l=sorted(l,reverse=True)
    print(50)
    for i in range(50):
        print(str(l[i])+" ",end="")
    print("")
    ret=0
solve(int(input()))
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint,time,random
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def cal(T):
    res = 0
    last = [0] * 26
    for day in range(D):
        t = T[day]; t -= 1
        last[t] = 0
        res += s[day][t]
        for i in range(26):
            if i == t: continue
            last[i] += 1
            res -= c[i] * last[i]
    return res
def check_change(td,tq):
    global score,res
    old_q = res[td]
    res[td] = tq
    now = cal(res)
    if now > score:
        score = now
    else:
        res[td] = old_q

start_time = time.time()
n = 26
D = inp()
c = inpl()
s = []
max_s = []
for i in range(D):
    tmp = inpl()
    mx = 0; ind = -1
    for j in range(n):
        if tmp[j] > mx:
            mx = tmp[j]
            ind = j
    max_s.append(ind+1)
    s.append(tmp)

last = [0] * n
res = [-1] * D
for d in range(D):
    ans = -1
    mx = -INF
    for i in range(n):
        now = s[d][i]
        for j in range(n):
            if i == j: continue
            now -= s[d][j] * (last[j]+1)
        if now > mx:
            mx = now
            ans = i
    res[d] = ans+1
    for j in range(n):
        last[j] += 1
        if j == ans: last[j] = 0
score = cal(res)
# print(now_score)
for x in itertools.combinations(range(D), 3):
    old = []
    for i in range(3):
        old.append(res[x[i]])
        res[x[i]] = max_s[x[i]]
    now = cal(res)
    if now > score:
        score = now
    else:
        for i in range(3):
            res[x[i]] = old[i]
while time.time() - start_time < 1.83:
    td,tq = random.randrange(0,D), random.randrange(1,n+1)
    check_change(td,tq)

for x in res:
    print(x)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = 26
D = inp()
c = inpl()
s = [inpl() for _ in range(D)]
last = [0] * n
res = [-1] * D
for d in range(D):
    ans = -1
    mx = -INF
    for i in range(n):
        now = s[d][i]
        for j in range(n):
            if i == j: continue
            now -= s[d][j] * (last[j]+1)
        if now > mx:
            mx = now
            ans = i
    res[d] = ans+1
    for j in range(n):
        last[j] += 1
        if j == ans: last[j] = 0
for x in res:
    print(x)
### BUGGY CODE ###

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

w = []
v = []

dp = [0] * (W+1)

for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        dp[j] = max(dp[j], DP)

print(max(dp))


### FIXED CODE ###

def dp():
    n, W = map(int, input().split())
    wv = (map(int, input().split()) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in wv:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(dp())
### BUGGY CODE ###

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

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
d = [0]*(n+1)
count = 0
for el, cnt in counter.most_common():
    d[el] = cnt
    count += cnt*(cnt-1)
count //= 2
for el in a:
    print(count - d[el] + 1)
### BUGGY CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    ans = 1
    for i in range(2, int(p ** (1 / n)) + 2):
        if p % (i ** n) == 0:
            ans = i
    print(ans)

### FIXED CODE ###

import collections

def prime_return(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, p = map(int, input().split())
t = collections.Counter(prime_return(p))
ans = 1
for k, v in t.items():
    if v >= n:
        ans *= (k ** (v // n))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = list(map(int, input().split()) for _ in range(q))

num = [0]*(10**5 + 1)
for i in range(10**5 + 1):
    num[i] = a.count(i)

s = sum(a)

for b, c in bc:
    s += (c - b)*num[b]
    num[c] += num[b]
    num[b] = 0

    print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = list(map(int, input().split()) for _ in range(q))

s = sum(a)

num = [0]*(10**5 + 1)
for x in a:
    num[x] += 1

for b, c in bc:
    s += (c - b)*num[b]
    num[c] += num[b]
    num[b] = 0

    print(s)
### BUGGY CODE ###

N, W = map(int, input().split())
knap = []

for i in range(N):
    knap.append(list(map(int, input().split())))
    
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if(j >= knap[i][0]):
            dp[i+1][j] = max(dp[i][j], dp[i][j-knap[i][0]]+knap[i][1])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
knap = []

for _ in range(N):
    knap.append(tuple(map(int, input().split())))
    
dp = np.zeros((N+1, W+1), dtype=np.int64)

for i, (w, v) in enumerate(knap):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
       
print(dp[N][-1])
### BUGGY CODE ###

n,k=map(int,input().split())
vr,vs,vp=map(int,input().split())
t=list(input())

rr=0
ss=1
pp=2

vsum=0
for i in range(k):
    ti=[t[ii] for ii in range(n) if ii%k==i]
    ni=len(ti)
    dp=[[0]*3 for i in range(ni+1)]
    for i2 in range(ni):
        if ti[i2]=="r":
            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
            dp[i2+1][pp]=max(dp[i2][rr]+vp,dp[i2][ss]+vp)
        elif ti[i2]=="s":
            dp[i2+1][rr]=max(dp[i2][ss]+vr,dp[i2][pp]+vr)
            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
        elif ti[i2]=="p":
            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
            dp[i2+1][ss]=max(dp[i2][pp]+vs,dp[i2][rr]+vs)
            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
    vsum+=max(dp[ni][rr],dp[ni][ss],dp[ni][pp])
print(vsum)
     

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,k=map(int,input().split())
vr,vs,vp=map(int,input().split())
t=list(input())

rr=0
ss=1
pp=2

vsum=0
for i in range(k):
#    ti=[t[ii] for ii in range(n) if ii%k==i]
#    ni=len(ti)
#    dp=[[0]*3 for i in range(ni+1)]
    dpir=0
    dpis=0
    dpip=0
    for i2 in range(i,n,k):
        if t[i2]=="r":
#            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
#            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
#            dp[i2+1][pp]=max(dp[i2][rr]+vp,dp[i2][ss]+vp)
            dpir2=max(dpis,dpip)
            dpis2=max(dpip,dpir)
            dpip2=max(dpir,dpis)+vp
        elif t[i2]=="s":
#            dp[i2+1][rr]=max(dp[i2][ss]+vr,dp[i2][pp]+vr)
#            dp[i2+1][ss]=max(dp[i2][pp],dp[i2][rr])
#            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
            dpir2=max(dpis,dpip)+vr
            dpis2=max(dpip,dpir)
            dpip2=max(dpir,dpis)
        elif t[i2]=="p":
#            dp[i2+1][rr]=max(dp[i2][ss],dp[i2][pp])
#            dp[i2+1][ss]=max(dp[i2][pp]+vs,dp[i2][rr]+vs)
#            dp[i2+1][pp]=max(dp[i2][rr],dp[i2][ss])
            dpir2=max(dpis,dpip)
            dpis2=max(dpip,dpir)+vs
            dpip2=max(dpir,dpis)
        dpir=dpir2
        dpis=dpis2
        dpip=dpip2
#    vsum+=max(dp[ni][rr],dp[ni][ss],dp[ni][pp])
    vsum+=max(dpir,dpis,dpip)
print(vsum)
### BUGGY CODE ###

n,m=map(int, input().split())
a=[int(input())  for i in  range(m)]
x=(10**9)+7

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1

for i in range(2,n+1):
  if i in a:
    continue
    
  if i-1 not in a:
    dp[i]+=dp[i-1]
  if i-2 not in a:
    dp[i]+=dp[i-2]
  #print(dp)
  
print(dp[-1]%x)

### FIXED CODE ###

n,m=map(int, input().split())
a=set(int(input())  for i in  range(m))
x=(10**9)+7

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1

for i in range(2,n+1):
  if i in a:
    continue
  dp[i]+=dp[i-1]+dp[i-2]
  #print(dp)
  
print(dp[-1]%x)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B,C,S = [0 for i in range(Q)],[0 for i in range(Q)],[0 for i in range(Q)]
for i in range(Q):
    B[i],C[i] = map(int,input().split())


for j in range(Q):
    b,c = B[j],C[j]
    for i in range(N):
        if A[i]==b:
            A[i] = c
        S[j] = S[j]+A[i]
    print(S[j])


### FIXED CODE ###

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

n = [0 for i in range(100001)]
S = 0
for i in range(N):
    n[A[i]] = n[A[i]] + 1
    S = S + A[i]

for i in range(Q):
    S = S + (C[i]-B[i])*n[B[i]]
    n[C[i]] = n[C[i]] + n[B[i]]
    n[B[i]] = 0
    print(S)
### BUGGY CODE ###

import math
import numpy as np
 
N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

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

l = -1
r = 10**12

def judge(c):
    s = 0
    for i in range(N):
        s += max(A_sort[i]-c//F_sort[i],0)
    return s <= K

while r-l > 1:
    c = (l+r)//2
    if judge(c):
        r = c
    else:
        l = c
print(max(r,0))

### FIXED CODE ###

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

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

l = -1
r = 0
for i in range(N):
    r = max(r,A_sort[i]*F_sort[i])

def judge(c):
    s = 0
    for i in range(N):
        s += max(A_sort[i]-c//F_sort[i],0)
    return s <= K

while r-l > 1:
    c = (l+r)//2
    if judge(c):
        r = c
    else:
        l = c
print(r)
### BUGGY CODE ###

S = input()
K = int(input())
anslist = []
for i in range(0, len(S)):
	now = str(S[i])
	if len(anslist) != K and now not in anslist:
		anslist.append(now)
	elif len(anslist) == K and now < anslist[-1] and now not in anslist:
		anslist[-1] = now
	anslist.sort()
	for j in range(i+1, len(S)):
		now = now + str(S[j])
		if len(anslist) != K and now not in anslist:
			anslist.append(now)
		elif len(anslist) == K and now < anslist[-1] and now not in anslist:
			anslist[-1] = now
		anslist.sort()
print(anslist[-1])

### FIXED CODE ###

S = input()
K = int(input())
anslist = []
for i in range(0, len(S)):
	now = ''
	for j in range(i, len(S)):
		now = now + str(S[j])
		flag = True
		if len(anslist) != K and now not in anslist:
			flag = False
			anslist.append(now)
		elif len(anslist) == K and now < anslist[-1] and now not in anslist:
			flag = False
			anslist[-1] = now
		elif now in anslist:
			flag = False
		anslist.sort()
		if flag:
			break
print(anslist[-1])
### BUGGY CODE ###

from numpy import *
from functools import lru_cache

H, W, D = map(int, input().split())
A = array([list(map(int, input().split())) for _ in range(H)])
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

dp = [0 for _ in range(H*W)]
for i in range(H*W) :
    (h,), (w,) = where(A==i+1)
    dp[i] = (h, w)

def f(p, q) :
    x, y = dp[p]
    i, j = dp[q]
    return abs(x-i)+abs(y-j)

distance = [0 for _ in range(H*W)]
for i in range(H*W) :
    if i<D :
        distance[i] = 0
    else :
        distance[i] = f(i-D, i) + distance[i-D]

for l, r in LR :
    print(distance[r-1]-distance[l-1])

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

dp = [None for _ in range(H*W)]
for i, l in enumerate(A) :
    for j, v in enumerate(l) :
        dp[v-1] = (i, j)

def f(p, q) :
    x, y = dp[p]
    i, j = dp[q]
    return abs(x-i)+abs(y-j)

distance = [0 for _ in range(H*W)]
for i in range(H*W) :
    if i<D :
        pass
    else :
        distance[i] = f(i-D, i) + distance[i-D]

for l, r in LR :
    print(distance[r-1]-distance[l-1])
### BUGGY CODE ###

S = list(input())
Q = int(input())
Q_l = []
for i in range(Q):
    Q_l.append(input().split())
for i in range(Q):
    #print(S)
    if int(Q_l[i][0]) == 1:
        S.reverse()
    else:
        if int(Q_l[i][1]) == 1:
            S = list(Q_l[i][2]) + S
        else:
            S.append(Q_l[i][2])
print("".join(S))

### FIXED CODE ###

S = list(input())
Q = int(input())
Q_l = []
for i in range(Q):
    Q_l.append(input().split())
rev_flg = 0
head_list =[]
tail_list = []
for i in range(Q):
    if int(Q_l[i][0]) == 1:
        rev_flg += 1
    else:
        if rev_flg % 2 == 0 and int(Q_l[i][1]) == 1:
            head_list.append(Q_l[i][2])
        elif rev_flg % 2 == 1 and int(Q_l[i][1]) == 1:
            tail_list.append(Q_l[i][2])
        elif rev_flg % 2 == 0 and int(Q_l[i][1]) == 2:
            tail_list.append(Q_l[i][2])
        else:
            head_list.append(Q_l[i][2])
head_list.reverse()
head_list.extend(S)
head_list.extend(tail_list)
if rev_flg %2 ==1:
    head_list.reverse()
print("".join(head_list))
### BUGGY CODE ###

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

for _ in range(M):
    As.sort()
    b, c = map(int, input().split())
    for i in range(b):
        if As[i] < c:
            As[i] = c
        else:
            break

print(sum(As))


### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
As.sort(reverse=True)

BCs = []
for _ in range(M):
    b, c = map(int, input().split())
    BCs.append({'b': b, 'c': c})

BCs = sorted(BCs, key=lambda bc: bc['c'], reverse=True)
#print(BCs)

new_cards = []
for i in range(M):
    new_cards += [BCs[i]['c'] for _ in range(BCs[i]['b'])]
    if len(new_cards) >= N:
        break

if len(new_cards) < N:
    new_cards += [0 for _ in range(N-len(new_cards))]
#print(new_cards)

A_index = 0
new_index = 0
new_As = []
for i in range(N):
    if As[A_index] >= new_cards[new_index]:
        new_As.append(As[A_index])
        A_index += 1
    else:
        new_As.append(new_cards[new_index])
        new_index += 1

print(sum(new_As))
### BUGGY CODE ###

import numpy as np
def dfs(start, G):
    stack = [start]
    visited = [0]*len(G)
    while stack:
        label = stack.pop(0)
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    

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


count = 0
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  v_temp = dfs(i,G)
  count += 1
  visit = np.logical_or(visit, v_temp)
  
  
print(count)

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**5+1)
input = sys.stdin.readline

def dfs(v,G,visit):
    visit[v-1]=1    
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        _ = dfs(next,G,visit) 
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0

visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    _ = dfs(i,G,visit)
  else:
    visit[i-1] = 1
  count += 1

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

n,a,b=map(int,input().split())
mod=10**9+7
bikkuri=[0 for i in range(n+5)]
bikkuri[0]=1
gyaku=[0 for i in range(n+5)]
gyaku[0]=1
for i in range(1,n+5):
    bikkuri[i] = (i * bikkuri[i-1])%mod
    gyaku[i]=pow(bikkuri[i], mod-2, mod)
def comb(a,b):
    return bikkuri[a]*gyaku[b]*gyaku[a-b]
ans=(2**n)-1-comb(n,a)-comb(n,b)
print(ans%mod)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
bunbo=1
bunshi=1
for i in range(1,max(a+1, b+1)):
    bunbo*=i
    bunshi*=n-i+1
    bunshi%=mod
    bunbo%=mod
    if i==a:
        comba=bunshi*(pow(bunbo,mod-2,mod))
    if i==b:
        combb=bunshi*(pow(bunbo,mod-2,mod))
print((2**n-1-comba-combb)%mod)
### BUGGY CODE ###

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

### FIXED CODE ###

import collections
n=int(input())
a=[int(_) for _ in input().split()]
l=[a[i]+i for i in range(n)]
r=[i-a[i] for i in range(n)]
c=collections.Counter(r)
ans=0
for i in range(n):ans+=c[l[i]]
print(ans)