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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

x = int(input())
a = 0
b = 0
flag = False
for i in range(10**7):
    tmp = ((x + i**5)**(1/5)).real
    if tmp.is_integer():
        b = i
        a = x + b**5
        flag = True
        break
if flag == False:
    for i in range(-10**7,0):
        tmp = ((x + i**5)**(1/5)).real
        if tmp.is_integer():
            b = i
            a = x + b**5
            flag = True
            break
print(int(a),int(b))


### FIXED CODE ###

x = int(input())
a = []
b = []
ansa = 0
ansb = 0
for i in range(10**3):
    a.append(i**5)
    b.append(i**5)
for i in a:
    for j in b:
        if i - j == x:
            ansa = i**(1/5)
            ansb = j**(1/5)
        elif i + j == x:
            ansa = i**(1/5)
            ansb = -(j**(1/5))
        elif -i + j == x:
            ansa = -(i**(1/5))
            ansb = -(j**(1/5))
        elif -i -j == x:
            ansa = -(i**(1/5))
            ansb = j**(1/5)
print(int(ansa), int(ansb))
### BUGGY CODE ###

import numpy as np

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

MOD = 10**9 + 7

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = []
for i in range(n):
    counter.append(list(format(a[i], 'b').zfill(max_digits))[::-1])  # 逆順にする 
cnt_arr = np.array(counter, dtype='int')

ans = 0
n_mod = n % MOD
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_mod = np.count_nonzero(cnt_arr[:, i]) % MOD
    radix_mod = 2**i % MOD
    ans += (radix_mod * one_mod * (n_mod - one_mod)) % MOD
print(ans % MOD)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

max_digits = 60
MOD = 10**9 + 7

ans = 0
for i in range(max_digits):
    one_num = np.count_nonzero((a >> i) & 1)
    radix_mod = 2**i % MOD
    ans += (radix_mod * one_num * (n - one_num)) % MOD
print(ans%MOD)
### BUGGY CODE ###

def f():
    import sys
    input=sys.stdin.buffer.readline
    inputs=sys.stdin.buffer.readlines
    sys.setrecursionlimit(10**9)
    n,m=map(int,input().split())
    edges=[[] for i in range(3+3*n)]
    for i in range(m):
        """#weighted->erase_,__,___=map(int,input().split())
        edges[_].append((__,___))
        #undirected->erase#edges[__].append((_,___))
        """
        _,__=map(int,input().split())
        _*=3;__*=3
        edges[_].append(__+1)
        edges[_+1].append(__+2)
        edges[_+2].append(__)

        #undirected->erase#edges[__].append(_)
        """
    """#weighted->erase

    s,T=map(int,input().split())
    from collections import deque
    dq=deque([])
    dq.append((3*s,0))
    T*=3
    seen=set()
    seen.add(3*s)
    while dq:
        now,c=dq.popleft()
        if now==T :print(c//3);exit()
        for t in edges[now]:
            if t not in seen:
                dq.append((t,c+1))
                seen.add(now)

    print("-1")
if __name__ == "__main__":
    f()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=[0]*(3*n+3)
seen[3*s]=1
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if seen[t]==0:
            dq.append((t,c+1))
            seen[t]=1
print("-1")
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = np.zeros(N, dtype='int32')

for _ in range(K):
    lights = np.zeros(N, dtype='int32')
    for i, flash in enumerate(A):
        front = i-flash if i-flash >= 0 else 0
        back = i+flash if i+ flash < N else N-1
        lights[front:back+1] += 1
    A = np.copy(lights)

for i in A:
    print(int(i),end=' ')
print()

### FIXED CODE ###

import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = [0] * N

for _ in range(min(K, 42)):
    lights = [0] * N
    for i, flash in enumerate(A):
        lights[max(0, i-flash)] += 1
        if i+flash < N-1:
            lights[i+flash+1] -= 1
    for i in range(1, N):
        lights[i] += lights[i-1]
    A = copy.deepcopy(lights)

for i in A:
    print(int(i),end=' ')
print()
### BUGGY CODE ###

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

for i in reversed(range(1, m//n+1)):
    if m % i == 0:
        print(i)
        exit()


### FIXED CODE ###

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

upper = m//n
ans = 0
for i in range(1, upper+1):
    if m % i == 0:
        ans = i
        if (m // i) > i and (m // i) <= upper:
            ans = m // i
            break

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


class Result:
    def __init__(self, num, result):
        self.num = num
        self.result = result


def WelcomeTo():
    N, M = map(int, input().split())
    resultlist = []
    WAcountlist = []
    for _ in range(M):
        templist = input().split()
        resultlist.append(Result(int(templist[0]), templist[1]))
    for _ in range(0, N + 1):
        WAcountlist.append(0)

    AClist = []
    WAcount = 0
    for lst in resultlist:
        if lst.num in AClist:continue

        if lst.result == 'AC':
            AClist.append(lst.num)
            WAcount += WAcountlist[lst.num]
        else:
            WAcountlist[lst.num] += 1


    print('{} {}'.format(len(AClist), WAcount))


WelcomeTo()


### FIXED CODE ###


class Question:
    def __init__(self, AC, WAcount):
        self.AC = AC
        self.WAcount = WAcount


def WelcomeTo():
    N, M = map(int, input().split())
    Qlist = []
    ACcount = 0
    WAcount = 0
    for _ in range(0, N + 1):
        Qlist.append(Question('False', 0))
    for _ in range(M):
        num, judge = input().split()
        num = int(num)
        if Qlist[num].AC == 'True':continue

        if judge == 'AC':
            ACcount += 1
            WAcount += Qlist[num].WAcount
            Qlist[num].AC = 'True'
        elif judge == 'WA':
            Qlist[num].WAcount += 1

    print('{} {}'.format(ACcount, WAcount))


WelcomeTo()
### BUGGY CODE ###

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

d = 10**9 + 7

ans = 0
for i in range(len(A) - 1):
    ans += A[i] * (sum(A[i+1:]))
print(ans % d)

### FIXED CODE ###

n = int(input())
A = input().split()
A = [int(t) for t in A]

d = 10**9 + 7
s = sum(A)
ans = 0
for i in range(len(A) - 1):
    s = s - A[i]
    ans += A[i] * (s)

print(ans % d)
### BUGGY CODE ###

import collections as c
d=c.defaultdict(list)
d2=c.defaultdict(list)
a,b,*q=map(int,open(0).read().split())
for s in range(b):
    g,j=q[2*s],q[2*s+1]
    d[g].append(j)
    d[g]=sorted(d[g])
for t in d.keys():
    for k,v in enumerate(d[t]):
        d2[t].append((v,k+1))
#print(d2)
for s in range(b):
    g,j=q[2*s],q[2*s+1]
    for sss in d2[g]:
        if sss[0]==j:
            print('{:06d}'.format(g)+'{:06d}'.format(sss[1]))

### FIXED CODE ###

a,b=map(int,input().split())
l=[]
for _ in range(b):
    c,d=map(int,input().split())
    l.append((c,d))
l2=sorted(sorted(l, key=lambda x:x[1]), key=lambda y:y[0])
m=1
count=0
dic={}
for t in l2:
    if t[0] !=m:
        m=t[0]
        count=1
    else:
        count+=1
    dic[t]=count
#print(dic)
for q in l:
    print('{:06d}'.format(q[0])+'{:06d}'.format(dic[q]))
### BUGGY CODE ###

# フェルマーの小定理
K = int(input())
S = input()

m = 1000000007

result = 0
a = 1
b = 1
t = pow(26, K, m)
inv26 = pow(26, m - 2, m)
for i in range(K + 1):
    # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
    result += t * (a * pow(b, m - 2, m))
    result %= m
    t *= inv26 * 25
    t %= m
    a *= len(S) - 1 + (i + 1)
    a %= m
    b *= i + 1
    b %= m
print(result)


### FIXED CODE ###

# フェルマーの小定理
K = int(input())
S = input()

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


fac = make_factorial_table(len(S) + K)

result = 0
for i in range(K + 1):
    result += pow(26, i, m) * mcomb(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, m)
    result %= m
print(result)
### BUGGY CODE ###

import math as m
N,M = map(int,input().split())
# N == 1 の処理
if N == 1:
    print(M)
    exit()
# Mの素数判定
judge = "prime"
for i in range(m.floor(pow(M,1/2)),1,-1):
    if M % i == 0:
        judge = "conposite"
        break
if judge == "prime":
    print(1)
    exit()
for i in range(M // N,0,-1):
    if M % i == 0:
        print(i)
        exit()

### FIXED CODE ###

import math as m
N,M = map(int,input().split())
# N == 1 の処理
if N == 1:
    print(M)
    exit()
# Mの素数判定
judge = "prime"
for i in range(m.floor(pow(M,1/2)),1,-1):
    if M % i == 0:
        judge = "conposite"
        break
if judge == "prime":
    print(1)
    exit()
for i in range(M // N,0,-1):
    if M % i == 0:
        print(i)
        exit()
### BUGGY CODE ###

import sys
from collections import deque


dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len, q_list):
    cnt = 0
    while True:
        new_q_list = []
        for q in q_list:
            h, w = q[0], q[1]
            for dx, dy in zip(dx_list, dy_list):
                x, y = w+dx, h+dy
                if m_list[y][x] == 0:
                    m_list[y][x] = 1
                    new_q_list.append([y, x])
        if len(new_q_list) == 0:
            break
        else:
            cnt += 1
            q_list = new_q_list
    return cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    m_list = [[1 for _ in range(w_len+2)]]
    for _ in range(h_len):
        s = input()[:-1]
        m_list.append([1] + [1 if i == '#' else 0 for i in s] + [1])
    m_list.append([1 for _ in range(w_len+2)])
    q_list = []
    for h, w_list in enumerate(m_list[1:-1]):
        for w, a in enumerate(w_list[1:-1]):
            if a == 1:
                q_list.append([h+1, w+1])
    ans = bfs(h_len, w_len, q_list)
    print(ans)
	

### FIXED CODE ###

def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)
### BUGGY CODE ###

n,k,q = map(int, input().split())
a =[int(input()) for i in range(q)]

point = [k]*n

for i in range(q):
    solver = a[i]-1

    for j in range(0,solver):
        point[j] -= 1

    for j in range(solver+1,n):
        point[j] -= 1

for i in range(n):
    if point[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for i in range(q)]

point = [0]*n

for i in range(q):
    point[a[i]-1] += 1

for i in range(n):
    if point[i] > q-k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import fractions

#inp = [int(i) for i in input().split()]
inp = int(input())

task = []
for e in range(inp):
    task.append([int(i) for i in input().split()])

    so = sorted(task,key=lambda x:x[1])

    ti = 0
    for dd in so:
        ti = dd[0] + ti
        if ti <= dd[1]:
            continue
        else:
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

import fractions

#inp = [int(i) for i in input().split()]
inp = int(input())

task = []
for e in range(inp):
    task.append([int(i) for i in input().split()])

so = sorted(task,key=lambda x:x[1])
ti = 0

for dd in so:
    ti = dd[0] + ti
    if ti <= dd[1]:
        pass
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

import sys

a, b = map(int, sys.stdin.readline().split())

ans = a
for i in range(b - a):
    ans = ans ^ (a + i + 1)
print(ans)


### FIXED CODE ###

import sys

a, b = map(int, sys.stdin.readline().split())


def check(x):
    if x % 4 == 0:
        return x
    elif x % 2 == 0:
        return x + 1
    elif (x+1)/2 % 2 == 0:
        return 0
    else:
        return 1


a = check(a-1)
b = check(b)
print(a ^ b)
### BUGGY CODE ###

x, y = [int(i) for i in input().split()]
if x % y == 0:
    print(-1)
else:
    i = 2
    while True:
        if i * x % y != 0:
            print(i * x)
            break


### FIXED CODE ###

x, y = [int(i) for i in input().split()]
if x % y == 0:
    print(-1)
else:
    i = 2
    while True:
        if i * x % y != 0:
            print(i * x)
            break
        i += 1
### BUGGY CODE ###

def solve():
    n=int(input())
    r=range
    a=list(map(int, input().split()))
    q=int(input())
    
    for _ in r(q):
        bi, ci = map(int, input().split())
        c=0
        for i in r(n):
            if a[i] == bi:
                a[i]=ci
            c+=a[i]
        print(c)


if __name__ == '__main__':
    t=1
    for _ in range(t):
        solve()


### FIXED CODE ###

def solve():
    n=int(input())
    r=range
    a=list(map(int, input().split()))
    q=int(input())

    d={}
    s=0
    for i in r(n):
        cu=a[i]

        if d.get(cu, None):
            d[cu]+=1
        else:
            d[cu]=1
        
        s+=cu
    
    for _ in r(q):
        bi, ci = map(int, input().split())
        diff=ci-bi

        if d.get(ci, None):
            d[ci]+=d.get(bi, 0)
        else:
            d[ci]=d.get(bi, 0)

        s+=diff * d.get(bi, 0)
        print(s)

        if d.get(bi, None):
            d[bi]=0


if __name__ == '__main__':
    t=1
    for _ in range(t):
        solve()
### BUGGY CODE ###

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = (3**N)

def main():
    dp1 = make2d_arr(N+1,SUM+1,0)
    dp3 = make2d_arr(N+1,SUM+1,0)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=2*dp3[n][s]
            if s>=a:
                dp1[n+1][s]+=dp1[n][s-a]
                dp3[n+1][s]+=dp3[n][s-a]
    S3 = sum(dp3[N][(SUM+1)//2:])*3
    S1 = dp1[N][(SUM)//2]*3 if SUM%2==0 else 0
    return (ALL - S3 + S1) % DIV

print(main())


### FIXED CODE ###

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = [0]*(SUM+1)
    dp3 = [0]*(SUM+1)
    dp1[0]=1
    dp3[0]=1
    
    for n in range(N):
        a = As[n]
        dp1 = [(dp1[s]+(dp1[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]
        dp3 = [(dp3[s]*2 + (dp3[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]

    S3 = (sum(dp3[(SUM+1)//2:])*3)%DIV
    S1 = (dp1[(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())
### BUGGY CODE ###

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

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

B = []
C = []
for _ in range(Q):
    B_i, C_i = map(int, input().split())
    
    B.append(B_i)
    C.append(C_i)

for i in range(Q):
    A = [(A[j] if A[j] != B[i] else C[i]) for j in range(len(A))]
    print(sum(A))


### FIXED CODE ###

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

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

B = []
C = []
for _ in range(Q):
    B_i, C_i = map(int, input().split())
    
    B.append(B_i)
    C.append(C_i)

max_i = max(max(A), max(C))

A_N = [0 for _ in range(max_i + 1)]
sum_i = 0

for a in A:
    A_N[a] += a
    sum_i += a

for i in range(Q):
    diff_replace = int(A_N[B[i]] / B[i]) * C[i]
    sum_i += diff_replace - A_N[B[i]]
    
    A_N[C[i]] += diff_replace
    A_N[B[i]] = 0
    
    print(sum_i)
### BUGGY CODE ###

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


p = 1
for i in range(K):
    p = p * A[i]

for i in range(K, N):
    pre = p
    p = (p // A[i - K]) * A[i]

    if (pre < p):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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


for i in range(K, N):
    if (A[i - K] < A[i]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)]for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = bin(a[i])
    k = list(map(int, k[:1:-1]))
    k = k + [0 for i in range(leng - len(k))]
    for j in range(leng):
        if k[j] == 1:
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

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

    As.sort()

    def isOK(x):
        num = 0
        for A in As:
            i = bisect_left(As, x-A)
            num += N-i
        return num >= M

    ng, ok = 10**10+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()


### FIXED CODE ###

from bisect import bisect_left, bisect_right

maxA = 10**5

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

As.sort()

def isOK(v):
    num = 0
    for A in As:
        i = bisect_left(As, v-A)
        num += N-i
    return num >= M

ng, ok = 2*maxA+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

accRevAs = [As[-1]]
for A in reversed(As[:-1]):
    accRevAs.append(accRevAs[-1]+A)
accRevAs.reverse()

v = ok
ans = 0
numGt = 0
#numEq = 0
for A in As:
#    iL = bisect_left(As, v-A)
    iR = bisect_right(As, v-A)
    if iR < N:
        ans += accRevAs[iR] + A*(N-iR)
    numGt += N-iR
#    numEq += iR-iL

ans += v * (M-numGt)
print(ans)
### BUGGY CODE ###

import math

def comb(n,r):
    if n-r<0:
        return 0
    return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))

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

nums=[0 for i in range(N+1)]

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

ans=[]
for i in range(N):
    number=0
    nums[A[i]]-=1
    for j in range(1,N+1):
        number+=comb(nums[j],2)
    ans.append(number)
    nums[A[i]]+=1

for i in range(N):
    print(ans[i])

### FIXED CODE ###

import math

def comb(n):
    if n-2<0:
        return 0
    return math.factorial(n)//(math.factorial(2)*math.factorial(n-2))
    
N=int(input())
A=list(map(int,input().split()))

nums=[0 for i in range(N+1)]
for i in range(N):
    nums[A[i]]+=1

num=0
for i in range(len(nums)):
    num+=comb(nums[i])

for i in range(N):
    ans=num-(nums[A[i]]-1)
    print(ans)
### BUGGY CODE ###

from functools import lru_cache


@lru_cache(None)
def factrial(n):
    ans = 1
    for i in range(1, n+1):
        ans *= i
    return ans


@lru_cache(None)
def combinations(n, r,mod):
    return (factrial(n) // (factrial(n - r) * factrial(r))) % mod


def main():
    n, k = map(int, input().split())
    mod = 10 ** 9 + 7
    A = tuple(map(lambda x: x % mod, sorted(map(int, input().split()))))
    ans = 0
    for i, a in enumerate(A[k - 1:], k - 1):
        ans += (a * combinations(i, k - 1,mod)) % mod
        ans %= mod
    for i, a in enumerate(A[: n - k + 1], 1):
        ans -= (a * combinations(n - i, k - 1,mod)) % mod
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from functools import lru_cache
n, k = map(int, input().split())
A = sorted(map(int, input().split()))
mod = 10 ** 9 + 7
# 階乗とその逆元の計算
factrial = [0 for _ in range(n + 1)]
factrial[0] = 1
for i in range(1, n + 1):
    factrial[i] = (factrial[i - 1] * i) % mod
inverse_factrial = list()
for f in factrial:
    inverse_factrial.append(pow(f, -1, mod))


@lru_cache(maxsize=None)
def nCr(n, r):
    return (factrial[n] * inverse_factrial[r] * inverse_factrial[n - r]) % mod


ans = 0
# 最大値の和
for i, a in enumerate(A[k - 1:], k - 1):
    ans += ((a % mod) * nCr(i, k-1)) % mod
    ans %= mod
# 最小値の和
A.reverse()
for i, a in enumerate(A[k - 1:], k - 1):
    ans -= ((a % mod) * nCr(i, k-1)) % mod
    ans %= mod
print(ans)