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

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

flag = 1 
cnt = 0 

for i in range(N):
        if i + 1 > len(A):
                break
        flag = 1 
        for j in reversed(range(i + 1, len(A))):
                if A[j] == A[i]:
                        flag = -1
                if A[j] % A[i] == 0:
                        del A[j]
        if flag == -1: 
                cnt += 1

print(len(A) - cnt)

### FIXED CODE ###

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

A.sort()

l = [0] * (A[N - 1] + 1)

for i in A:
        j = i 
        while j <= A[N - 1]: 
                l[j] += 1
                j += i 

cnt = 0 
for k in A:
        if l[k] == 1:
                cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
cnt = 1
for i in range(n-1):
  s = sum(a[:i+1])
  #print(s)
  for j in range(i+1,n):
    if s*2 >= a[j] :
      s += a[j]
      #print(s)
    else:
      break
  if s == sum(a):
    cnt += 1
print(cnt)

### FIXED CODE ###

import itertools
n = int(input())
a = list(map(int,input().split()))
a.sort()
#print(a)[1, 2, 7, 20, 30, 40]
A = list(itertools.accumulate(a))
#print(A)[1, 3, 10, 30, 60, 100]
cnt = 0
for i in range(n-1):
  s = A[i]
  #この条件を満たしていないとそれ以上他のスライムを取り込めない
  if s*2 < a[i+1] :
    cnt = i+1

print(n-cnt)
### BUGGY CODE ###


def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    if Lock[A[i][id[i]]-1] == i and i not in tmp:
                        Lock[A[i][id[i]]-1] = -1
                        id[A[i][id[i]]-1] += 1
                        tmp.add(A[i][id[i]]-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)


main()


### FIXED CODE ###

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 1.9:
            ans = M
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()
### BUGGY CODE ###

from collections import deque, defaultdict

def solve(N, M, paths):
    used = [False for _ in range(M)]
    stack = deque([1])
    ret = [[float("inf"), -1] for _ in range(N + 1)]
    ret[1] = [0, 1]

    while stack:
        cur = stack.popleft()
        nexts = paths[cur]
        for n in nexts:
            if used[n[0]]:
                continue
            used[n[0]] = True
            stack.append(n[1])
            if ret[cur][0] + 1 < ret[n[1]][0]:
                ret[n[1]] = [ret[cur][0] + 1, cur]

    print("Yes")
    for r in ret[2:]:
        print(r[1])

if __name__ == "__main__":
    N, M = map(int, input().split())
    paths = defaultdict(list)
    for idx in range(M):
        a, b = map(int, input().split())
        paths[a].append([idx, b])
        paths[b].append([idx, a])

    solve(N, M, paths)

### FIXED CODE ###

from collections import deque, defaultdict

def solve(N, M, paths):
    used = [False for _ in range(M)]
    stack = deque([1])
    ret = [[float("inf"), -1] for _ in range(N + 1)]
    ret[1] = [0, 1]

    while stack:
        cur = stack.popleft()
        nexts = paths[cur]
        for n in nexts:
            if used[n[0]]:
                continue
            used[n[0]] = True
            if ret[cur][0] + 1 < ret[n[1]][0]:
                ret[n[1]] = [ret[cur][0] + 1, cur]
                stack.append(n[1])

    print("Yes")
    for r in ret[2:]:
        print(r[1])

if __name__ == "__main__":
    N, M = map(int, input().split())
    paths = defaultdict(list)
    for idx in range(M):
        a, b = map(int, input().split())
        paths[a].append([idx, b])
        paths[b].append([idx, a])

    solve(N, M, paths)
### BUGGY CODE ###

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

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i < k:
            break
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])

### FIXED CODE ###

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

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i < k:
            break
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])
### BUGGY CODE ###

ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y

n = ini()
a = inl()
ans = 1
lim = 10 ** 18
for i in a:
        ans *= i
if ans > lim:
        ans = -1
print(ans)


### FIXED CODE ###

import math
import re
import copy
import sys

n = int(input())
a = list(map(int,input().split()))
ceil = 10 ** 18
ans = 1
if all([b > 0 for b in a]):
    for i in range(n):
        ans *= a[i]
        if ans > ceil:
            break
if any([b == 0 for b in a]):
    print(0)
elif ans > ceil:
    print("-1")
else:
    print(ans)
### BUGGY CODE ###

X,Y=map(int,input().split())
print(X+Y//2)
for i in range(20**7):
  i+=1



### FIXED CODE ###

X,Y=map(int,input().split())
print(X+Y//2)
### BUGGY CODE ###

s = input()
n = len(s)

if s[0] == '0' or s[-1] == '1':
    print(-1)
    exit()
for i in range(n-1):
    if s[i] != s[-2-i]:
        print(-1)
        exit()

path = {1:[v for v in range(2, n+1)]}
u_cur, v_cur = 1, 2
for i in range(n//2-1, 0, -1):
    if s[i] == '1':
        path[v_cur] = []
        for _ in range(i):
            v_tar = path[u_cur].pop()
            path[v_cur].append(v_tar)
        u_cur, v_cur = v_cur, path[v_cur][0]
for u, vs in path.items():
    for v in vs:
        print(*(u, v))


### FIXED CODE ###

s = input()
n = len(s)

if s[0] == '0' or s[-1] == '1':
    print(-1)
    exit()
for i in range(n-1):
    if s[i] != s[-2-i]:
        print(-1)
        exit()

path = {1:[v for v in range(2, n+1)]}

ans = []
u_cur, v_cur = 1, 2
n_prev = 0
for i in range(1, n//2):
    if s[i] == '1':
        for _ in range(i-n_prev):
            ans.append((u_cur, v_cur))
            v_cur += 1
        ans.append((v_cur, u_cur))
        u_cur, v_cur = v_cur, v_cur+1
        n_prev = i+1
for v in range(v_cur, n+1):
    ans.append((v_cur-1, v))
for a in ans:
    print(*a)
### BUGGY CODE ###

def calculate(n, m, id_list):
  result = 0
  for i in range(1, n+1):
    is_passed = True
    for id_list_index in range(0, m):
      if not((i >= id_list[id_list_index][0]) and (i <= id_list[id_list_index][1])) :
        is_passed = False
        
    if is_passed:
      result = result + 1
    
  return result
  
  
import sys

n=0
m=0
id_list=[]
is_arg_ok = False
try:
  n, m  = map(int, input().split())
  for i in range(0, m):
    gate_min, gate_max = map(int, input().split())
    id_list.append([gate_min, gate_max])
  is_arg_ok = True
  
except:
  print('arg error')
  sys.exit(1)

calculated_num = calculate(n, m, id_list)
print(calculated_num)
sys.exit(0)



### FIXED CODE ###

import sys
n=0
m=0

n, m  = map(int, input().split())
_min, _max  = map(int, input().split())
for i in range(1, m):
  gate_min, gate_max = map(int, input().split())
  if (_max > gate_max):
    _max = gate_max
   
  if _min < gate_min:
    _min = gate_min
 
result_list = list(filter(lambda x : (_min <= x) and (x <= _max), range(1, n+1)))
result = len(result_list)

print(result)
sys.exit(0)
### BUGGY CODE ###

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

dp = [10**9] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
        else:
            break
print(dp[n - 1])

### FIXED CODE ###

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

dp = [10**9] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
        else:
            break
print(dp[n - 1])
### BUGGY CODE ###

import heapq, math, sys

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
maxA = A[0]
pre = -1
while len(A) != pre:
    if len(A) == 0:
        print(math.ceil(maxA))
        sys.exit()
    pre = len(A)
    meanA = math.ceil(sum(A)/(len(A)+K))
    for i, a in enumerate(A):
        if a <= meanA:
            A = A[:i]
            break


cuts = [0]*(i+1)
meanA = math.ceil(sum(A)/(len(A)+K))
for i, a in enumerate(A):
    cut_at_least = (a//meanA -1)
    cuts[i] = cut_at_least
    K -= cut_at_least
hq = [(-a/(cut+1), i) for i, (a, cut) in enumerate(zip(A, cuts))]
heapq.heapify(hq)
for _ in range(K):
    l, i = heapq.heappop(hq)
    cuts[i] += 1
    heapq.heappush(hq, (-A[i]/(cuts[i]+1), i))
l, i = heapq.heappop(hq)
print(math.ceil(-l))


### FIXED CODE ###

import heapq, math, sys

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
maxA = A[0]
pre = -1
while len(A) != pre:
    if len(A) == 0:
        print(math.ceil(maxA))
        sys.exit()
    pre = len(A)
    meanA = math.ceil(sum(A)/(len(A)+K))
    for i, a in enumerate(A):
        if a <= meanA:
            A = A[:i]
            break


cuts = [0]*(i+1)
meanA = (sum(A)/(len(A)+K))
for i, a in enumerate(A):
    cut_at_least = (math.floor(a/meanA) - 1)
    cuts[i] = cut_at_least
    K -= cut_at_least
hq = [(-a/(cut+1), i) for i, (a, cut) in enumerate(zip(A, cuts))]
heapq.heapify(hq)
lenhq = len(hq)
for k in range(K):
    l, i = heapq.heappop(hq)
    cuts[i] += 1
    if k <= N:
        heapq.heappush(hq, (-A[i]/(cuts[i]+1), i))
l, i = heapq.heappop(hq)
print(math.ceil(-l))
### BUGGY CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

print('\n'.join(map(str, answer)))
# 19

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

print('\n'.join(map(str, answer)))
# 19
### BUGGY CODE ###

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

if 2 not in A:
  print(-1)
  exit()

a = A[0]
while a != 2: 
  if a == 1:
    print(-1)
    exit()
  a = A[a-1]
  cnt += 1
  if a == 1:
    print(-1)
    exit()
print(cnt)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
cnt = 0

if 2 not in a:
  print(-1)
  exit()

x = 1
for i in range(n-1):
 
  x = a[x-1]
  cnt += 1

            
  if x == 2:
    print(cnt)
    exit()

print(-1)
### BUGGY CODE ###

import numpy as np

H, W, D = map(int, input().split())
pos = [None]*(H*W)

for i in range(H):
    row = list(map(int, input().split()))
    for j in range(W):
        pos[row[j]-1] = (i, j)

costs = [0]*(H*W)
for i in range(1, D+1):
    current = i + D
    while current <= H*W:
        costs[current - 1] = costs[current - 1 - D] + np.absolute(pos[current - 1][0] - pos[current - 1 - D][0]) + np.absolute(pos[current - 1][1] - pos[current - 1 - D][1])
        current += D

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    MP = costs[R-1] - costs[L-1]
    print(MP)

### FIXED CODE ###

H, W, D = map(int, input().split())
pos = [None]*(H*W)

for i in range(H):
    row = list(map(int, input().split()))
    for j in range(W):
        pos[row[j]-1] = (i, j)

costs = [0]*(H*W)
for i in range(1, D+1):
    current = i + D
    while current <= H*W:
        costs[current - 1] = costs[current - 1 - D] + abs(pos[current - 1][0] - pos[current - 1 - D][0]) + abs(pos[current - 1][1] - pos[current - 1 - D][1])
        current += D

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    MP = costs[R-1] - costs[L-1]
    print(MP)
### BUGGY CODE ###

import itertools

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

def tri_d(a,b,c):
  if (a+b>c) and (b+c>a) and (c+a>b):
    return True
  else:
    return False


ans=0
C=list(itertools.combinations(L, 3))
for a,b,c in C:
  if tri_d(a,b,c):
    ans+=1
print(ans)

### FIXED CODE ###

import bisect

N=int(input())
L=list(map(int, input().split()))
L=sorted(L)

count=0
for i in range(N-2):
  a=L[i]
  for j in range(i+1, N-1):
    b=L[j]
    r=bisect.bisect_left(L, a+b)
    count+=r-1-j
    
print(count)
### BUGGY CODE ###

import math
N=int(input())
ans=0
for i in range(1,N+1):
  Y=math.floor(N/i)
  ans+=(Y*(Y+1)*i)//2
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
    largest = N // i * i
    ans += ((largest + i) * (N // i)) // 2
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter, deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, q = map(int, input().split())

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

    cnt = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p - 1] += x

    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            cnt[u] += cnt[v]
            dfs(u, v)

    dfs(0, -1)
    print(*cnt)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

ans = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        else:
            ans[u] += ans[v]
            dfs(u, v)

dfs(0, -1)
print(*ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n, x = map(int, input().split())
  BLU = [list(map(int, input().split())) for _ in range(n)]
  B, L, U = zip(*BLU)
  S = [b*l+(x-b)*u for b, l, u in BLU]
  sortedS = sorted([(s, i) for i, s in enumerate(S)], reverse=True)
  S, idx = zip(*sortedS)
  B = [B[i] for i in idx]
  L = [L[i] for i in idx]
  U = [U[i] for i in idx]
  M = sum([b*l for b, l, u in BLU])

  def select(q, r):
    f = sum(S[:q+1])
    for i in range(n):
      temp = f - S[min(i, q)]
      temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
      if temp>=M:
        return True
    return False

  ng = -1
  ok = sum(B)
  while ok-ng > 1:
    mid = (ok+ng)//2
    q, r = divmod(mid, x)
    if select(q, r):
      ok = mid
    else:
      ng = mid
  print(ok)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

"""

重要度はlかuしかとらないと考えてよい
高橋君のほうが青木君より低い点数を取ると決めた科目に対してはl、それ以外はuと定める
それぞれのテストの点数の差をdとして、Σ[a>=b](d*u) - Σ[a<b](d*l) >= 0 を満たす
最小のΣaを求める
→各iについて、biまではli個ずつ減らすことができ、それより多く減らす場合はXを超えない範囲で
 ui個ずつ減らすことができる
→heapqでできそう
 単純なheapqだと、例えば一つのテストの中でlとuの値の差がとても大きい時に
 正しい答えが出せない
→二分探索

"""
import sys
input = sys.stdin.readline

n, x = map(int, input().split())
BLU = [list(map(int, input().split())) for _ in range(n)]
SBLU = sorted([(b*l+(x-b)*u, b, l, u) for b, l, u in BLU], reverse=True)
S, B, L, U = zip(*SBLU)
M = sum([b*l for b, l, u in BLU])

def select(q, r):
  f = sum(S[:q+1])
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False


ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ov = 10**9+7
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x
l = lcm(a)
b= [l//i%ov for i in a]
print(sum(b)%ov)


### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N,M = map(int,input().split())
P = []
Y = []
P_Y = []
for i in range(N):
  P_Y.append([])

for i in range(M):
  p,y = map(int,input().split())
  P.append(p-1)
  Y.append(y)
  P_Y[p-1].append(y)
  
for i in range(N):
 P_Y[i].sort()

for i in range(M):
  ID1 = "{0:06d}".format(P[i]+1)
  tmp = P_Y[P[i]].index(Y[i])
  ID2 = "{0:06d}".format(tmp + 1)
  print(ID1 + ID2)

### FIXED CODE ###

N, M = map(int, input().split())
P_Y = []
for i in range(M):
   p,y = map(int,input().split())
   P_Y.append([p-1,y,i])
#n次元リストのソート
#普通にsort()をつけると1番目の要素でソート
#1番目の要素が同じ場合は2番目の要素の大小によってソートされる
P_Y.sort() 

ans_P_Y = [] 
count = 1
for i in range(M):
  if(i != 0):
    if(P_Y[i-1][0] == P_Y[i][0]): count += 1
    else: count = 1
  ans_P_Y.append([P_Y[i][2],P_Y[i][0]+1,count])
ans_P_Y.sort()

for i in range(M):
  ans = str(ans_P_Y[i][1]).zfill(6) + str(ans_P_Y[i][2]).zfill(6)
  print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = list(map(int,input().split()))
uf = UnionFind(N)
p = list(map(int,input().split()))
L = []
for i in range(M):
    x,y = map(int,input().split())
    uf.union(x - 1,y - 1)
cnt = 0
for x in uf.all_group_members().values():
    tmp = []

    for y in x:
        tmp.append(p[y]-1)
    for y in x:
        if y in tmp:
            cnt+=1
print(cnt)



### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = list(map(int,input().split()))
uf = UnionFind(N)
p = list(map(int,input().split()))
L = []
for i in range(M):
    x,y = map(int,input().split())
    uf.union(x - 1,y - 1)
cnt = 0
for i in range(N):
    if uf.same(i,p[i]-1):
        cnt+=1
print(cnt)
### BUGGY CODE ###

from math import factorial

n,k=map(int,input().split())
a=sorted(list(map(int, input().split())))
s=0

#maxについて
for i in range(k-1,n):
	s+=(a[i]*factorial(i)//factorial(k-1)//factorial(i-k+1))%(10**9+7)
	s%=10**9+7
for i in range(n-k+1):
	s-=(a[i]*factorial(n-i-1)//factorial(k-1)//factorial(n-k-i))%(10**9+7)
	s%=10**9+7
print(s)


### FIXED CODE ###

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
    
n,k=map(int,input().split())
a=sorted(list(map(int, input().split())))
MOD=10**9+7

fac, ifac=make_tables(MOD,n)

s=0
for i in range(k-1,n):
	s+=(a[i]-a[n-i-1])*cmb(i,k-1,MOD,fac,ifac)
	s%=10**9+7
print(s)