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

N,M = map(int,input().rstrip().split(" "))
A = list(map(int,input().rstrip().split(" ")))
A.sort(reverse = True)
Q = []
for i in range(M):
    B,C = map(int,input().rstrip().split(" "))
    Q.append([C,B])
Q.sort(reverse = True)

P = [0 for _ in range(len(A)) ]
p = 0
j = 0
while p < len(A) and j < M:
    for _ in range(Q[j][1]):
        A.append(Q[j][0])
    p += Q[j][1]
    j += 1
ans = 0
A.sort(reverse = True)
for i in range(N):
    ans += A[i]

print(ans)

### FIXED CODE ###

N,M = map(int,input().rstrip().split(" "))
A = list(map(int,input().rstrip().split(" ")))
A.sort(reverse = True)
Q = []
for i in range(M):
    B,C = map(int,input().rstrip().split(" "))
    Q.append([C,B])
Q.sort(reverse = True)

p = 0
j = 0
while p < N and j < M:
    for i in range(Q[j][1]):
        if i + p > N:
            break
        A.append(Q[j][0])
    p += Q[j][1]
    j += 1
ans = 0
A.sort(reverse = True)

for i in range(N):
    ans += A[i]

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

x = int(input())
n=100
tes = [0]
for i in range(-10001,10001):
    for j in range(-10001,10001):
        if pow(i,5) - pow(j,5) == x:
            print(str(i)+" "+str(j))
            exit()

### FIXED CODE ###

x = int(input())
n=100
tes = [0]
for i in range(-250,250):
    for j in range(-250,250):
        if pow(i,5) - pow(j,5) == x:
            print(str(i)+" "+str(j))
            exit()
### BUGGY CODE ###

from collections import deque
def main():
    n, m, k = map(int, input().split())
    friends = {k: set() for k in range(1, n + 1)}
    foe = {k: set() for k in range(1, n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = map(int, input().split())
        foe[a].add(b)
        foe[b].add(a)

    belong_group = [-1] * (n + 1)
    groups = {}
    stack = deque()
    group_num = 1
    nodes_seen = set()
    for i1 in range(1, n + 1):
        if i1 in nodes_seen or friends[i1] == []:
            continue
        else:
            belong_group[i1] = group_num
            groups[group_num] = set()
            groups[group_num].add(i1)
            nodes_seen.add(i1)
            stack += friends[i1]
            while stack:
                next_node = stack.popleft()
                if next_node in nodes_seen:
                    continue
                else:
                    nodes_seen.add(next_node)
                    belong_group[next_node] = group_num
                    groups[group_num].add(next_node)
                    stack += friends[next_node]
            group_num += 1
    for i2 in range(1, n + 1):
        r = max(len(groups[belong_group[i2]] - friends[i2] - foe[i2]) - 1, 0)
        print(r, end=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    num_of_friends = [-1] * n
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        num_of_friends[a] += -1
        num_of_friends[b] += -1
    roots = defaultdict(int)
    #roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)] += 1
    for i3 in range(n):
        #num_of_friends[i3] += len(roots[find(i3)])
        num_of_friends[i3] += roots[find(i3)]
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1

    for i in range(n):
        print(num_of_friends[i], end=' ')

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

from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mods = [0] * P
        mods[0] = 1
        current = 0
        x = 1
        for s in S:
            current = (current + x * int(s)) % P
            ans += mods[current % P]
            mods[current % P] += 1
            x = x * 10 % P
    print(ans)

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

H,W,K = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0]*(W) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "1":
            L[i][j] = 1
        
ans = H*W
for i in range(2**(H-1)):
    cnt = 0
    used = [0]*W
    memo = []
    for j in range(H-1):
        if i & (1<<j):
            cnt += 1
            memo.append(j+1)
    memo.append(H)
    num = [0]*(cnt+1)
    for j in range(W):
        idx = 0
        for k in range(H):
            if memo[idx] == k:
                idx += 1
            num[idx] += L[k][j]
        f = False
        for k in range(len(num)):
            if num[k] > K:
                f = True
                break
        if f:
            if j == 0 or used[j-1] == 1:
                cnt = H*W
                break
            used[j-1] = 1
            cnt += 1
            num = [0]*len(num)
            idx = 0
            for k in range(H):
                if memo[idx] == k:
                    idx += 1
                num[idx] += L[k][j]
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

H,W,K = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0]*(W) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "1":
            L[i][j] = 1
        
ans = H*W
for i in range(2**(H-1)):
    cnt = 0
    used = [0]*W
    memo = []
    for j in range(H-1):
        if i & (1<<j):
            cnt += 1
            memo.append(j+1)
    memo.append(H)
    num = [0]*(cnt+1)
    for j in range(W):
        idx = 0
        for k in range(H):
            if memo[idx] == k:
                idx += 1
            num[idx] += L[k][j]
        f = False
        for k in range(len(num)):
            if num[k] > K:
                f = True
                break
        if f:
            if j == 0 or used[j-1] == 1:
                cnt = H*W
                break
            used[j-1] = 1
            cnt += 1
            num = [0]*len(num)
            idx = 0
            for k in range(H):
                if memo[idx] == k:
                    idx += 1
                num[idx] += L[k][j]
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

import itertools

K,S = map(int,input().split())

cnt = 0
for i in list(itertools.product(range(K+1),repeat = 3)):
    if sum(i) == S:
        cnt += 1
print(cnt)

### FIXED CODE ###

K,S = map(int,input().split())
ans = 0
for i in range(K+1):
    for j in range(K+1):
        Z = S - i - j
        if(j>=0 and i>=0 and Z>=0 and K>=Z and S == i + j + Z):
            ans += 1
print(ans)
### BUGGY CODE ###

import functools
import operator

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

t = functools.reduce(operator.mul, a)

if t > 10**18 :
    print(-1)
else:
    print(t)

### FIXED CODE ###

import numpy as np

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

if any([i == 0 for i in a]):
    print('0')
else:
    for i in range(n):
        x = a[i]
        t = t * x
        if x == 0:
            break
        if t > 10**18:
            break

    if t > 10**18:
        print('-1')
    else:
        print(t)
### BUGGY CODE ###

N = int(input())

cnt = 0
S_list = [input() for _ in range(N)]


def count_symmetry(S_symmetry):
    for i in range(N):
        for j in range(N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    S_symmetry = S_list[k:] + S_list[:k]
    if count_symmetry(S_symmetry):
        cnt += 1

print(cnt * N)


### FIXED CODE ###

N = int(input())
S_list = [input() for _ in range(N)]
cnt = 0


def count_symmetry(S_symmetry):
    for i in range(N):
        for j in range(i + 1, N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    S_symmetry = S_list[k:] + S_list[:k]
    if count_symmetry(S_symmetry):
        cnt += 1

print(cnt * N)
### BUGGY CODE ###

L = input()
ans = 0
n = len(L)
def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
count = 0
for i in range(len(L)):
    if i == 0:
        ans += (pow(3,n-1) + 2) % 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (pow(3,n-1)+1)%1000000007*(pow(2,count)%1000000007)
            count += 1
    n -= 1
print(ans%1000000007)


### FIXED CODE ###

L = input()
ans = 0
n = len(L)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

count = 0
for i in range(len(L)):
    if i == 0:
        ans += (power_func(3,n-1,1000000007) + 2)
        ans %= 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (power_func(3,n-1,1000000007)+1)*(power_func(2,count,1000000007))
            ans %= 1000000007
            count += 1
    n -= 1
print(ans%1000000007)
### BUGGY CODE ###

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

q = int(input())
pl = primes(10**5)
ql = [p*2-1 for p in pl if p*2-1 in pl and p*2-1<=10**5+1]
for _ in range(q):
  l,r = map(int,input().split())
  fil = list(filter(lambda x: l<=x<=r, ql))
  print(len(fil))

### FIXED CODE ###

import itertools

def prime_boolean_table(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, n + 1):
        if primes[i]:
            for j in range(i + i, n + 1, i):
                primes[j] = False
    return primes

pl = prime_boolean_table(10**5)
ql = [0]*(10**5+1)
for i in range(1,10**5+1):
    if pl[i] and pl[(i+1)//2]:
        ql[i] += 1
ql = list(itertools.accumulate(ql))
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    print(ql[r]-ql[l-1])
### BUGGY CODE ###

LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    for k in range(n // 2):
        r += mck * pow(2, k, LARGE)
        r %= LARGE
        mck *= n - k
        mck %= LARGE
        mck *= pow(k + 1, LARGE - 2, LARGE)
        mck %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    factorial_n = 1
    factorial_inv = [0] * (n + 1)
    factorial_inv[0] = 1
    for i in range(1, n + 1):
        factorial_n *= i
        factorial_n %= LARGE
    factorial_inv[-1] = pow(factorial_n, LARGE - 2, LARGE)
    for i in range(n):
        factorial_inv[n - i - 1] = (factorial_inv[n - i] * (n - i)) % LARGE
    pow_2 = 1
    for k in range(n // 2):
        r += factorial_n * factorial_inv[n - k] * factorial_inv[k] * pow_2
        r %= LARGE
        pow_2 *= 2
        pow_2 %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


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

A, B = map(int, input().split())

ans = []
for k in range(len(bin(10**12))-2):
    one = 0
    for i in range(A, B+1):
        x = (i >> k) & 1
        if x == 1: one += 1
    if one % 2 == 0:
        ans += '0'
    else:
        ans += '1'
ans.reverse()
print(int(''.join(ans), 2))

### FIXED CODE ###

A, B = map(int, input().split())

def f(n, k):
    if n < 0:
        return 0
    if n // 2**k == 0:
        if n >= 2**(k-1):
            return n - 2**(k-1) + 1
        else:
            return 0
    else:
        return int((n // 2**k) * (2**(k-1))) + f(n-(n // 2**k)*(2**k), k)

ans = []
for k in range(1, len(bin(10**12))-1):
    b = f(B, k)
    a = f(A-1, k)
    one = b-a
    if one % 2 == 0:
        ans += '0'
    else:
        ans += '1'

ans.reverse()
print(int(''.join(ans), 2))
### BUGGY CODE ###

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

def solve(l, ans):
	if l == []:
		return ans

	cnd = [] 
	for i in range(len(l)):
		if l[i] == i+1:
			cnd.append(i)

	if cnd == []:
		return 0

	for ind in cnd:
		ans.append(ind+1)
		cond = solve(l[0:ind] + l[(ind+1):(len(l)+1)], ans)
		if cond == 0:
			ans.pop()
			continue
		else:
			return cond


	return 0	

ans = solve(a,[])

if ans == 0:
	print(-1)
else:
	for A in ans[::-1]:
		print(A)

### FIXED CODE ###

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

ans = []

for i in range(n):
    for j in range(len(B)-1, -1, -1):
        if B[j] == j+1:
            ans.append(B.pop(j))
            break
    else:
        print(-1)
        break
else:
    for a in ans[::-1]:
        print(a)
### BUGGY CODE ###

NK = list(map(int, input().split()))
N = NK[0]
K = NK[1]
count = 0


for k in range(K, N):
	for b in range(k+1, N+1):
		for i in range(0, N+1):
			a = i*b + k
			if a > N:
				break
			elif a != 0:
				count += 1

print(count)


### FIXED CODE ###

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

answer = 0

if K == 0:
	answer = N*N
else:
	for b in range(K+1, N+1):
		add = N//b * max(b-K, 0) + max(N%b+1-K, 0)
		answer += add

print(answer)
### BUGGY CODE ###

N=int(input())
print(sum(range(1, N)))


### FIXED CODE ###

N=int(input())
print(sum(range(1, N)))
### BUGGY CODE ###

from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    h=np.array(list(map(int,readline().split())),dtype=np.int64)
    before=np.arange(1,k+1,dtype=np.int64)
    zero=np.zeros(k,dtype=np.int64)

    dp=np.zeros(n,dtype=np.int64)
    for i in range(n):
        tmp=np.maximum(zero,i-before)
        dp[i]=(dp[tmp]+np.abs(h[i]-h[tmp])).min()

    print(dp[n-1])

if __name__=="__main__":
    main()


### FIXED CODE ###

def main():
    N,K=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[10**10]*N
    dp[0]=0
    for i in range(N):
        for j in range(1,min(K+1,N-i)):
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
    print(dp[N-1])

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

import math
n=int(input())
l=list(map(int,input().split()))
d={}
for i in l:
    if i in d:
        d[i]+=1 
    else:
        d[i]=1 
#print(d)
for i in l:
    count=0
    for k in d.keys():
        if k==i :
            x=d[k]
            if x<3:
                continue
            x-=1
            count+=math.factorial(x)/(math.factorial(x-2)*2)
        else:
            x=d[k]
            if x<2:
                continue
            count+=math.factorial(x)/(math.factorial(x-2)*2)
    print(int(count))        

### FIXED CODE ###

import math
n=int(input())
l=list(map(int,input().split()))
d={}
for i in l:
    if i in d:
        d[i]+=1 
    else:
        d[i]=1 
count=0
for k in d.keys():
        x=d[k]
        if x<2:
            count+=0
        else:
            count+=x*(x-1)//2

for i in l:
    x=d[i]
    #print(i, x)
    if x>=2:
        val=x*(x-1)//2
        ans=count-val
        if x>=3:
            x-=1
            val1=x*(x-1)//2
        else:
            val1=0
        ans+=val1
    else:
        if x==2:
            ans=count-1 
        else:
            ans=count 
    print(int(ans))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
max_x=max(A)+2
min_x=min(A)-1
l=set()
for x in range(min_x,max_x):
    cnt=0
    for a in A:
        if abs(x-a)<=1:
            cnt+=1
    l.add(cnt)
print(max(l))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[0]*(max(A)+3)
for a in A:
    ans[a-1]+=1
    ans[a]+=1
    ans[a+1]+=1
print(max(ans))
### BUGGY CODE ###

N, M, QN = [int(x) for x in input().split()]

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

for i in range(M):
    l, r = [int(x) for x in input().split()]
    MAT0[l][r] += 1

MAT = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(0, N + 1):
        MAT[i][j] = MAT[i][j - 1] + MAT0[i][j]

for i in range(QN):
    p, q = [int(x) for x in input().split()]
    ret = 0
    for j in range(p, q + 1):
        ret = ret + MAT[j][q] - MAT[j][p - 1]
    print(ret)


### FIXED CODE ###

N, M, QN = [int(x) for x in input().split()]

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

for i in range(M):
    l, r = [int(x) for x in input().split()]
    MAT0[l][r] += 1

MAT = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        MAT[i][j] = MAT[i][j - 1] + MAT0[i][j]

MM = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        MM[i][j] = MM[i - 1][j] + MAT[i][j]

for i in range(QN):
    p, q = [int(x) for x in input().split()]
    ret = 0
    ret = ret + MM[q][q] - MM[q][p - 1] - MM[p - 1][q] + MM[p - 1][p - 1]
    print(ret)
### BUGGY CODE ###

N = int(input())
T = [int(input()) for _ in range(N)]

T = sorted(list(set(T)))

T_max = T[len(T) - 1]
count = 1
flag_1 = True
while flag_1:
    check = T_max * count 
    flag_2 = True
    for i in T:
        if check % i != 0:
            flag_2 = False
            break
    if flag_2 == True:
        print(T_max * count)
        flag_1 = False
    count += 1

### FIXED CODE ###

N = int(input())
T = [int(input()) for _ in range(N)]

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
      
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
print(lcm_list(T))
### BUGGY CODE ###

# D
N, K = map(int, input().split())
lst = list(map(int, input().split()))
ma = 0
idx = 0
for i in range(len(lst)-(K-1)):
    if (ma < sum(lst[i:i+K])):
        ma = sum(lst[i:i+K])
        idx = i
ans = 0
for i in lst[idx:idx+K]:
    ans += (i+1) / 2 
print(ans)


### FIXED CODE ###

# D
N, K = map(int, input().split())
lst = list(map(int, input().split()))
lst1 = [(lst[0] + 1) / 2]
ma = 0
for i in range(1, len(lst)):
    lst1.append(lst1[i-1] + ((lst[i]+1) / 2))
    if (i >= K):
        ma = max(ma,lst1[i] - lst1[i-K])
ma = max(ma,lst1[K-1])
print(ma)
### BUGGY CODE ###

N = int(input())
A = [0 * x for x in range(N)]
B = [0 * x for x in range(N-1)]

for i in range(N):
  A[i] = int(input())

for i in range(N):
  M = max(A)
  if A[i] == M:
    M = max(A[:i]+A[i+1:])
  print (M)


### FIXED CODE ###

N = int(input())
A = [0 * x for x in range(N)]
B = [0 * x for x in range(N-1)]

for i in range(N):
  A[i] = int(input())

flag = False
M = max(A)
if A.count(M) > 1:
  flag = True
for i in range(N):
  if A[i] == M:
    if flag:
      print (M)
    else:
      print(max(A[:i]+A[i+1:]))
  else:
    print (M)
### BUGGY CODE ###

A,B= map(int, input().split())
now_sum = A
ans = 1
while True:
     if now_sum >= B:
         print(ans)
     now_sum += A-1
     ans += 1
print(ans)

### FIXED CODE ###

A,B= map(int, input().split())
now_sum = 1
ans = 0
while True:
     if  now_sum >= B:
         print(ans)
         break
     now_sum += A-1
     ans += 1
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = [0]*M
C = [0]*M
for i in range(M):
    ab[i] = list(map(int, input().split()))
    C[i] = set(map(int, input().split()))

treasure = set(range(1, N+1))
MAX = 1000000
cost_ans = MAX
for i in range(2**M):
    cost = 0
    set_treasure = set()
    for j in range(M):
        if ((i>>j) & 1):
            cost += ab[j][0]
            set_treasure = set_treasure.union(C[j])
    if set_treasure == treasure:
        cost_ans = min(cost_ans, cost)
           
if cost_ans == MAX:
    print(-1)
else:
    print(cost_ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
MAX = 1000000

N, M = map(int, input().split())
ab = [0]*M
C = [0]*M
for i in range(M):
    ab[i] = list(map(int, input().split()))
    c = list(map(int, input().split()))
    for cc in c:
        C[i] += (1<<(cc-1)) # bit

dp = [[MAX]*(2**N) for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
#    for p in range(M):
#        print(dp[p])
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j|C[i]] = min(dp[i+1][j|C[i]], dp[i][j]+ab[i][0])

res = dp[-1][-1]
if res == MAX:
    print(-1)
else:
    print(res)
### BUGGY CODE ###

import itertools


N, M = map(int, input().split())
edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

res = 0
if M < N - 1:
    print(res)
else:
    for course in itertools.combinations(edges, N - 1):

        num_of_v = [0] * N
        for edge in course:
            num_of_v[edge[0]] += 1
            num_of_v[edge[1]] += 1
        if num_of_v[0] != 1 and max(num_of_v) != 2:
            continue

        for root in itertools.permutations(course):
            vertex = [False] + [True] * (N - 1)
            v = 0
            for edge in root:
                if v in edge:
                    nv = edge[0] if v == edge[1] else edge[1]
                    if vertex[nv]:
                        vertex[nv] = False
                        v = nv
                        continue
                break
            else:
                res += 1
    print(res)


### FIXED CODE ###

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

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


def dfs(node, track):
    if len(track) == N:
        global res
        res += 1
    else:
        for dst in [x for x in edges[node] if x not in track]:
            dfs(dst, track + tuple([dst]))


res = 0
dfs(0, tuple([0]))
print(res)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    # from collections import deque
    N = int(input())
    A = list(map(int, input().split()))

    count = 0
    for now in range(N):
        for v in range(now+1, N):
            if A[now]+A[v] == v-now:
                count += 1
    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import numpy as np
    from collections import Counter
    N = int(input())
    A = np.array(list(map(int, input().split())))

    count = 0

    tmp = np.arange(N)
    X = A-tmp
    Y = A+tmp

    # print(X)
    # print(Y)
    XX = Counter(list(X))
    YY = Counter(list(Y))

    count = 0
    # print(XX)
    # print(YY)
    for number, c in XX.items():
        count += YY[-number] * c
        # count +=
    print(count)


if __name__ == "__main__":
    main()