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

def integerCards(n, m, alist, bclist):

    count = 0
    alist.sort()
    bclist.sort(key=lambda x: x[1], reverse=True)

    for b, c in bclist:
        for _ in range(b):
            if alist[count] < c:
                alist[count] = c
                count += 1
            if count == n:
                break
        if count == n:
            break

    return sum(alist)

def main():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))
    bclist = [list(map(int, input().split()))for i in range(m)]
    print(integerCards(n, m, alist, bclist))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def integerCards(n, m, alist, bclist):

    count = 0
    alist.sort()
    bclist.sort(key=lambda x: x[1], reverse=True)

    for b, c in bclist:
        for _ in range(b):
            if alist[count] < c:
                alist[count] = c
                count += 1
            else:
                break
            if count == n:
                break
        if count == n:
            break

    return sum(alist)

def main():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))
    bclist = [list(map(int, input().split()))for i in range(m)]
    print(integerCards(n, m, alist, bclist))

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

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**18

def bfs(start):
    d = [INF]*n
    d[start] = 0
    q = collections.deque([])
    q.append(start)
    pre = [0]*(n)
    while q:
        c = q.popleft()
        next_v = edge[c]
        for v in next_v:
            if v == 0 and start != 0:
                d[v] = d[c]+1
                pre[v] = c
                return [pre,d]
            if d[v] == INF and v != c:
                q.append(v)
                d[v] = d[c]+1
                pre[v] = c
    #経路を復元したい
    return [pre,d]
n,m = map(int,input().split())
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
judge = bfs(0)
flag = judge[1]
for i in flag:
    if i == INF:
        print("No")
        sys.exit()
print("Yes")
for i in range(1,n):
    ans = bfs(i)
    if ans[1][0] == 1:
        print("1")
    else:
        print(ans[0][0] + 1)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**18

def bfs(start):
    d = [INF]*n
    d[start] = 0
    q = collections.deque([])
    q.append(start)
    pre = [0]*(n)
    while q:
        c = q.popleft()
        next_v = edge[c]
        for v in next_v:
            if v == 0 and start != 0:
                d[v] = d[c]+1
                pre[v] = c
                return [pre,d]
            if d[v] == INF and v != c:
                q.append(v)
                d[v] = d[c]+1
                pre[v] = c
    #経路を復元したい
    return [pre,d]
n,m = map(int,input().split())
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
ans = bfs(0)
judge = ans[1]
for i in judge:
    if i == INF:
        print("No")
        sys.exit()
print("Yes")
for i in range(1,n):
    print(ans[0][i]+1)
### BUGGY CODE ###

expected_value_dic = {}

def get_expected_value(x):
    return (1 + x) / 2

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

P = list(map(int, input().split()))
expected_values = [get_expected_value(p) for p in P]

selected_array = [expected_values[i] for i in range(k)]
max_sum = sum(selected_array)
for i in range(k, len(P)):
    del selected_array[0]
    selected_array.append(expected_values[i])
    array_sum = sum(selected_array)
    if array_sum > max_sum:
        max_sum = array_sum


print(max_sum)


### FIXED CODE ###

expected_value_dic = {}

def get_expected_value(x):
    return (1 + x) / 2

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

P = list(map(int, input().split()))
expected_values = [get_expected_value(p) for p in P]
cumulative_values = [expected_values[0]]
for expected_value in expected_values[1:]:
    cumulative_values.append(cumulative_values[-1] + expected_value)

result = cumulative_values[k-1]
for i in range(k, n):
    temp = cumulative_values[i] - cumulative_values[i - k]
    if temp > result:
        result = temp

print(result)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    k = I()
    seen = set()
    for i in range(len(s)):
        curS = s[i]
        seen.add(curS)
        for j in range(i+1, len(s)):
            curS += s[j]
            seen.add(curS)
    print(sorted(list(seen))[k-1])

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    K = I()
    subs = set()
    for j in range(1, 6):
        for i in range(len(s)):
            st = i
            en = min(st + j, len(s))
            subs.add(s[st:en])
    print(sorted(list(subs))[K-1])
main()
### BUGGY CODE ###

S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = []
for i in range(0, N+1):
    for j in range(i, N+1):
        b = 0
        for k in range(i, j):
            b = b * 10 + h[k]
        a.append(b)
c = 0
for m in range(0, len(a)):
    if a[m] != 0 and a[m] % 2019 == 0:
        c += 1
print(c)

### FIXED CODE ###

S = input()
P = 2019
N = len(S)
num = [0] * P
num[0] = 1
c = 0
ans = 0
dgt = 1
for i in range(N-1, -1, -1):
    c = (c + int(S[i]) * dgt) % P
    dgt *= 10
    dgt %= P
    ans += num[c]
    num[c] += 1

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

n = int(input())
cnt = 0
for i in range(n):
    x = int(input())
    j = 2
    flag = 0
    while j <= x ** 1/2:
        if x % j == 0:
            flag = 1
            break
        j += 1
    if flag == 0:
        cnt += 1
print(cnt)


### FIXED CODE ###

import math


def isprime(x):
    for i in range(2,int(math.sqrt(x)) + 1):
        if x % i == 0:
            return 0
    return 1


n = int(input())
cnt = 0
for i in range(n):
    x = int(input())
    if isprime(x):
        cnt += 1
print(cnt)
### BUGGY CODE ###

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

C = N // (A + B) * A
D = N % (A + B)

E = 0
for i in range(D):
    if 0 < (i + 1) % (A + B) <= A:
        E += 1
        
print(C+E)

### FIXED CODE ###

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

C = N // (A + B) * A
D = N % (A + B)

if 0 <= D and D <= A:
    print(C + D)
else:
    print(C + A)
### BUGGY CODE ###

def level(x):
    L.append('B')
    if x>1:
        level(x-1)
    else:
        L.append(L0)
    L.append('P')
    if x>1:
        level(x-1)
    else:
        L.append(L0)
    L.append('B')


N,X = map(int,input().split())
count=0
L0 = 'P'
L = []
level(N)
for i in range(X):
    if L[i]=='P':
        count+=1

print(count)


### FIXED CODE ###

N,X = map(int,input().split())
a,p = [1],[1]

for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def f(N,X):
    if N == 0:
        return 0 if X<=0 else 1
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1]+1+f(N-1,X-2-a[N-1])

print(f(N,X))
### BUGGY CODE ###

L = input().split()
N = int(L[0])
A = int(L[1])
B = int(L[2])
blue = 0
for i in range(N):
    if i % (A + B) >= 0 and i % (A + B) <= (A - 1):
        blue += 1
print(blue)

### FIXED CODE ###

In = input().split()
N = int(In[0])
A = int(In[1])
B = int(In[2])
x = N // (A + B)
y = N - (A + B)*x
ans = x * A
if y <= A:
    ans += y
else:
    ans += A
print(ans)
### BUGGY CODE ###

from collections import defaultdict as dd

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = dd(int)
  zeros = dd(int)
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        ones[i] += 1
      else:
        zeros[i] += 1

  res = 0
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        res += zeros[i] * 2 ** i
        ones[i] -= 1
      else:
        res += ones[i] * 2 ** i
        zeros[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for i in range(60):
    res += ones[i] * (N - ones[i]) * ((2 ** i) % MOD)
    res %= MOD
  print(res)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# C - Subarray Sum
n, k, s = map(int, input().split())
arr = [s] * k

for i in range(n - k):
	arr.append(s + 1)

ans = ''

for a in arr:
	ans += str(a) + ' '

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# C - Subarray Sum
n, k, s = map(int, input().split())
ans = ''
str_s = str(s)

if s < pow(10, 9):
	str_another = str(s + 1)
else:
	str_another = '1'

for i in range(n):
	if i < k:
		ans += str_s + ' '
	else:
		ans += str_another + ' '

print(ans[:len(ans)-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
a = sorted(list(set(A)),reverse = True)
B = []
for k in range(len(a)):
    i = a[k]
    if A.count(i) >= 4:
        if len(B) == 0:
            print(i**2)
            exit()
        else:
            B.append(i)
            if len(B) >= 2:
                print(B[0]*B[1])
                exit()

    if A.count(i) >= 2:
        B.append(i)
        if len(B) >= 2:
            print(B[0]*B[1])
            exit()
if len(B) <= 1:
    print(0)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections

n = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
l = c.most_common()
L = [ l[i] for i in range(len(l)) if l[i][1] >= 2 ]
b = sorted(L,reverse = True)
if len(b) == 0:
    ans = 0
elif len(b) == 1 and b[0][1] < 4:
    ans = 0
else:
    if b[0][1] >= 4:
        ans = b[0][0]**2
    else:
        ans = b[0][0]*b[1][0]
print(ans)
### BUGGY CODE ###

def t(n, k, q, a):
    p = [k] * n
    for i in range(q):
        for j in range(n):
            if a[i]-1 != j:
                p[j] -= 1
    return ['Yes' if i > 0 else 'No' for i in p]


if __name__ == "__main__":
    n, k, q = map(int, input().split())
    a = [int(input()) for i in range(q)]
    r = t(n, k, q, a)
    for i in r:
        print(i)


### FIXED CODE ###

def t(n, k, q, a):
    p = [-q + k] * n
    for i in range(q):
        p[a[i-1]-1] += 1
    return ["Yes" if i > 0 else "No" for i in p]
   

if __name__ == "__main__":
    n, k, q = map(int, input().split())
    a = [int(input()) for i in range(q)]
    r = t(n, k, q, a)
    for i in r:
        print(i)
### BUGGY CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
dp=[[[False for i in range(80*160)] for j in range(w)] for k in range(h)]
dp[0][0][d[0][0]] = True
for i in range(h):
    for j in range(w):
        for dis in range(80*(h+w)):
            if dp[i][j][dis]:
                if i+1<h:
                    dp[i+1][j][dis+d[i+1][j]]=True
                    dp[i+1][j][abs(dis-d[i+1][j])]=True
                if j+1<w:
                    dp[i][j+1][dis+d[i][j+1]]=True
                    dp[i][j+1][abs(dis-d[i][j+1])]=True
for dis in range(80*(h+w)):
    if dp[-1][-1][dis]:
        print(dis)
        break

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
maxd=1
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
        maxd=max(maxd,d[i][j])
dp=[[0 for j in range(w)] for k in range(h)]
c=20000
dp[0][0] |= 1 << c+d[0][0]
for i in range(h):
    for j in range(w):
        if i+1<h:
            dp[i+1][j] |= dp[i][j] << d[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d[i+1][j]
        if j+1<w:
            dp[i][j+1] |= dp[i][j] << d[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d[i][j+1]
m=1000000
cnt = 0
for x in bin(dp[h-1][w-1])[2:][::-1]:
    if x=='1':
        m=min(m,abs(cnt-c))
    cnt+=1
print(m)
### BUGGY CODE ###

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

prev = 0
point = 1
ans = []
for i in range(N):
    if i < K:
        point *= A[i]
    else:
        prev = point
        point *= A[i]
        point /= A[i-K]
        if prev < point:
            ans.append("Yes")
        else:
            ans.append("No")
print(*ans, sep='\n') 


### FIXED CODE ###

from sys import stdin
readline = stdin.readline

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

prev = 0
point = 1
ans = []
for i in range(N):
    if i >= K:
        if A[i-K] < A[i]:
            ans.append("Yes")
        else:
            ans.append("No")
print(*ans, sep='\n')
### BUGGY CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
for i in range(m):
    k = A.index(max(A))
    A[k] //= 2
print(sum(A))


### FIXED CODE ###

import heapq
n,m = map(int,input().split())
A = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)

for i in range(m):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp_min//2))
print(-sum(A))
### BUGGY CODE ###

import math,collections

def f(c):
  sum=0
  for i in c.values():
    sum+=i*(i-1)//2
  return sum

n=int(input())
k=list(map(int,input().split()))
c=collections.Counter(k)

for i in range(n):
  c[k[i]]-=1
  print(f(c))
  c[k[i]]+=1


### FIXED CODE ###

import collections
n=int(input())
k=list(map(int,input().split()))
c=collections.Counter(k)
ans=0

for i in c.values():
  ans+=i*(i-1)//2

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

N = int(input())
str_to_int = {"W":0, "E":1}
input_ = input()
row = [str_to_int[input_[n]] for n in range(N)]

min_change_count = N+1
for n in range(N):
    west_side = row[:n]
    east_side = row[n:]
    count = len(west_side) - sum(west_side)
    count += sum(east_side)
    
    if count < min_change_count:
        min_change_count = count
        
print(min_change_count)

### FIXED CODE ###

N = int(input())
str_to_int = {"W":0, "E":1}
input_ = input()
row = [str_to_int[input_[n]] for n in range(N)]

min_change_count = N+2

west_cum_sum = 0
east_cum_sum = 0
west_cum_sums = []
east_cum_sums = []
for n in range(N):
    if row[n] == 0:
        west_cum_sum += 1
    if row[N-n-1] == 1:
        east_cum_sum += 1
    west_cum_sums.append(west_cum_sum)
    east_cum_sums.append(east_cum_sum)
    
east_cum_sums = east_cum_sums[::-1]
    
min_count = min(east_cum_sums[1], west_cum_sums[N-2])
for n in range(1, N-1):
    count = west_cum_sums[n-1] + east_cum_sums[n+1]
    if count < min_count:
        min_count = count
        
print(min_count)
### BUGGY CODE ###

from collections import defaultdict
import sys
S=input()
N=len(S)
if N==3:
    if S[0]==S[1]:
        if S[1]==S[2]:
            print(1)
        else:
            print(6)
    else:
        if S[0]==S[2]:
            print(7)
        elif S[1]==S[2]:
            print(6)
        else:
            print(3)
    sys.exit()
mod=998244353
M=0
for s in S:
    if s=='b':
        M+=1
    elif s=='c':
        M+=2
    M%=3
dd=defaultdict(int)
for i in range(3):
    dd[(0,i,i)]=1
for k in range(2,N+1):
    nd=defaultdict(int)
    for p,n in dd.items():
        con,moji,m=p
        #print(con,moji,m)
        if con==0:
            for k in range(3):
                if moji==k:
                    nd[(1, k, (m + k) % 3)] += n
                    nd[(1, k, (m + k) % 3)] %=mod
                else:
                    nd[(0,k,(m+k)%3)]+=n
                    nd[(0, k, (m+k) % 3)] %=mod
        else:
            for k in range(3):
                nd[(1, k, (m + k) % 3)] += n
                nd[(1, k, (m + k) % 3)] %=mod
    #print(nd)
    dd=nd
flag=1
for i in range(N-1):
    if S[i]==S[i+1]:
        flag=0
ans=flag
for p, n in dd.items():
    con, moji, m = p
    if m==M and con==1:
        ans+=n
        ans%=mod
print(ans)






### FIXED CODE ###

from collections import defaultdict
import sys
S=input()
N=len(S)
if N==3:
    if S[0]==S[1]:
        if S[1]==S[2]:
            print(1)
        else:
            print(6)
    else:
        if S[0]==S[2]:
            print(7)
        elif S[1]==S[2]:
            print(6)
        else:
            print(3)
    sys.exit()
a=S[0]
t=1
for i in range(N):
    if S[i]!=a:
        t=0
        break
if t==1:
    print(1)
    sys.exit()

mod=998244353
M=0
for s in S:
    if s=='b':
        M+=1
    elif s=='c':
        M+=2
    M%=3
dp=[]
for i in range(2):
    for k in range(3):
        for l in range(3):
            dp.append((i,k,l))
dd=[[[0]*3 for i in range(3)] for i in range(2)]
for i in range(3):
    dd[0][i][i]=1
for k in range(2,N+1):
    nd=[[[0]*3 for i in range(3)] for i in range(2)]
    for p in dp:
        con,moji,m=p
        n=dd[con][moji][m]
        #print(con,moji,m)
        if con==0:
            for k in range(3):
                if moji==k:
                    nd[1][k][ (m + k) % 3] += n
                    nd[1] [k ][(m + k) % 3] %=mod
                else:
                    nd[0][k][(m+k)%3]+=n
                    nd[0][ k] [(m+k) % 3] %=mod
        else:
            for k in range(3):
                nd[1][k][(m + k) % 3] += n
                nd[1][k][(m + k) % 3] %=mod
    #print(nd)
    dd=nd
flag=1
for i in range(N-1):
    if S[i]==S[i+1]:
        flag=0
ans=flag
for k in range(3):
    ans+=dd[1][k][M]
    ans%=mod
print(ans)
### BUGGY CODE ###

N = input()
N = int(N)

A = input().split()

ans = []
for i in range(len(A)):
    ans.append(0)

for a in A:
    ans[int(a)-1] = A.index(a)+1

for i in ans:
    print(i, end=" ")


### FIXED CODE ###

N = input()
N = int(N)
ans = [0]*N
A = input().split()

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

for i in ans:
    print(i, end=" ")
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N = int(input())
S = list(str(input()))

# R,G,B ひとつずつ
# 距離が等間隔でない

R_pos = []
G_pos = []
B_pos = []
for i in range(N):
    if S[i] == "R":
        R_pos.append(i)
    elif S[i] == "G":
        G_pos.append(i)
    elif S[i] == "B":
        B_pos.append(i)

answer = 0
for r in R_pos:
    for g in G_pos:
        for b in B_pos:
            dis1 = abs(r-g)
            dis2 = abs(g-b)
            dis3 = abs(b-r)
            if dis1 != dis2 and dis2 != dis3 and dis3 != dis1:
                answer += 1
print(answer)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N = int(input())
S = list(str(input()))

# R,G,B ひとつずつ
# 距離が等間隔でない

R_pos = []
G_pos = []
B_pos = []
for i in range(N):
    if S[i] == "R":
        R_pos.append(i)
    elif S[i] == "G":
        G_pos.append(i)
    elif S[i] == "B":
        B_pos.append(i)

answer = len(R_pos) * len(G_pos) * len(B_pos)
for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            answer -= 1

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

import sys
from collections import deque

sys.setrecursionlimit(10 ** 5 + 100)

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
root = set(range(n))
for line in sys.stdin.readlines():
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    root.discard(b)
root = root.pop()

parents = [-1] * n
q = deque([(root, -1)])

while q:
    v, p = q.popleft()
    parents[v] = p
    q.extend((c, v) for c in links[v])

print('\n'.join(str(p + 1) for p in parents))


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 5 + 100)

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
root = set(range(n))
for line in sys.stdin.readlines():
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    root.discard(b)
root = root.pop()

parents = [set() for _ in range(n)]
q = deque([(root, -1)])

while q:
    v, p = q.popleft()
    parents[v].add(p)
    if len(parents[v]) > 1:
        continue
    q.extend((c, v) for c in links[v])

fixed = [-1] * n

# print(parents)

q = deque([(root, -1)])
while q:
    v, p = q.popleft()
    pv = parents[v]
    pv.remove(p)
    if len(pv) == 0:
        fixed[v] = p
        q.extend((c, v) for c in links[v])

print('\n'.join(str(p + 1) for p in fixed))
### BUGGY CODE ###


import sys

def prime(q):
    count = 0
    for i in xrange(1,q+1):
        if i == 2:
            count += 1
        if pow(2, i-1, i) == 1:
            count += 1
    return count 


if __name__ == "__main__":
    for i in sys.stdin:
        x = int(i)
        print prime(x)
        

### FIXED CODE ###

import sys
n=10**6
p=[1]*n
p[0],p[1]=0,0
for i in xrange(2,int(n**0.5)+1):
    if p[i]==1:
        for j in xrange(i**2,n,i):
            p[j]=0
for i in xrange(2,n):
    p[i]+=p[i-1]
for line in sys.stdin.readlines():
    print p[int(line)]
### BUGGY CODE ###

from functools import reduce

N, result = eval(input()), 1
List = list(map(int, input().split()))
result = reduce(lambda x, y: x * y, List)
print(result if result <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
res = 1
if 0 in List:
    print(0)
    quit()
for x in List:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

n = int(input())
num_l=sorted(map(int,input().split()),reverse=True)
s=sorted(set(num_l),reverse=True)
d={i:num_l.count(i) for i in s}
res=[]
#c=max()
for i in num_l:
    if len(res) == 2:
        print(res[0]*res[1])
        break
    if d[i] >= 2:
        d[i]-=2
        res.append(i)
    else:
        pass
else:print(0)

### FIXED CODE ###

from collections import Counter
n = int(input())
num_l = sorted(map(int, input().split()),reverse=True)
s = sorted(set(num_l), reverse=True)
d = Counter(num_l) # {i:num_l.count(i) for i in s}
res = []
it = 0
lim=len(s)
# c = max()
for i in range(n):
    if d[s[it]] >= 2:
        d[s[it]]-=2
        res.append(s[it])
    else:
        it+=1#pass
        
    if len(res) == 2:
        print(res[0] * res[1])
        break
    if lim==it:
        print(0)
### BUGGY CODE ###

n = int(input())
l = [i+1 for i in range(n)]
print(sum(l)-max(l))

### FIXED CODE ###

n = int(input())
print((1 + n-1)*(n-1)//2)