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

n, k = (int(x) for x in input().split())
p = [int(x) for x in input().split()]
p_sum = [sum(p[i:i+k]) for i in range(len(p)-k+1)]
idx = p_sum.index(max(p_sum))
print(sum([(p_i*(p_i+1))/2 / p_i for p_i in p[idx:idx+k]]))

### FIXED CODE ###

n, k = (int(x) for x in input().split())
p = [int(x) / 2 + 0.5 for x in input().split()]
ans_i = ans = sum(p[:k])
i = 0
while i < n - k:
    ans_i = ans_i - p[i] + p[i+k]
    ans = max(ans, ans_i)
    i += 1
print(ans)
### BUGGY CODE ###

N = int(input())

S = []
for i in range(0,N):
    if i > 0:
        Value = input()
        Flag = False
        for j in range(len(S)):
            if S[j] == Value:
                Flag = True
                break

        if Flag == False:
            S.append (Value)

    else:
        S.append (input())

print(len(S),end='\n')

### FIXED CODE ###

N = int(input())

S = []
for i in range(N):
    S.append (input())

print(len(set(S)),end='\n')
### BUGGY CODE ###

def resolve():
  N, M = map(int, input().split(" "))
  H = [int(x) for x in input().split(" ")]

  AB = []
  for i in range(M):
    AB.append([int(x) for x in input().split(" ")])

  result = []
  for h_index in range(1, N+1):
    if len(AB) == 0:
      break

    result.append([])
    for ab in AB:
      if ab[0] == h_index:
        if ab[1] not in result[-1]:
          result[-1].append(ab[1])

      if ab[1] == h_index:
        if ab[0] not in result[-1]:
          result[-1].append(ab[0])

  # print(result)
  count = 0
  for h_index in range(0, N):
    flag = True
    for r in result[h_index]:
      if H[r-1] >= H[h_index]:
        flag = False
        break
    if flag:
      count += 1
  print(count)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N, M = map(int, input().split(" "))
  H = [int(x) for x in input().split(" ")]

  AB = []
  for i in range(M):
    AB.append([int(x)-1 for x in input().split(" ")])

  result = [True] * N
  for ab in AB:
    if H[ab[0]] > H[ab[1]]:
      result[ab[1]] = False
      continue
    if H[ab[1]] > H[ab[0]]:
      result[ab[0]] = False
      continue
    if H[ab[1]] == H[ab[0]]:
      result[ab[0]] = False
      result[ab[1]] = False
      continue

  print(result.count(True))

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

from collections import deque
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
distance = [0]*(n-1)
for i in range(n):
    queue = deque()
    visited = [0]*n
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k in range(len(visited)):
        if k > i:
            if visited[k] >= 1:
                distance[visited[k]-1] += 1
for l in distance:
    print(l)

### FIXED CODE ###

from collections import deque
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
# print(g)
distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
for i in range(n):
    queue = deque()
    visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k in range(len(visited)):
        if k > i:
            if visited[k] >= 1:
                distance[visited[k]-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
for l in distance:
    print(l)
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
ans = 0
for i in range(1,N+1):
  score = 0
  score = math.floor(A*i/B) -A* math.floor(i/B)
  ans = max(ans,score)
print(ans)

### FIXED CODE ###

A,B,N = map(int,input().split())
x = min(N,B-1)
print( int(A*x/B))
### BUGGY CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]

  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub == 0:
        #dp[i + 1][j] += 2 ** (i) % 998244353
        dp[i + 1][j] += int(pow(2,i,998244353))
      if sub > 0 and dp[i][sub]:
        dp[i + 1][j] += dp[i][sub]
  #print(dp)
  print(dp[length][target] % 998244353)
  
solve(N, S, A)

### FIXED CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 1
  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  #print(dp)
  print(dp[length][target])
  
solve(N, S, A)
### BUGGY CODE ###

N = int(input())

ans = 0
for c in range(1, N):
    X = N - c

    for a in range(1, int(X**0.5)+1):
        if X%a == 0:
            ans += 1
            if X/a != a:
                ans += 1

print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
for a in range(1, N):
    ans += (N-1)//a

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

import bisect
N = int(input())  # N<= 4000 6*10^10なので、削減しないとだめ
S = list(input())


# Si Sj Skがどれも別のもの。ただしi<j<k
# また、j-i != k-j
# 1,2,3はだめ1,2,4はok
# 1,3,5もだめ
# この組の数を求める

# count = 0
# for i in range(N):
#     for j in range(i + 1, N):
#         for k in range(j + 1, N):
#             if j - i != k - j:
#                 if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
#                     count += 1


indexes = {'R': [], "G": [], "B": []}
for i, char in enumerate(S):
    indexes[char].append(i + 1)
# print(permutation_hash)
count = 0
R_indexes_count = len(indexes['R'])
G_indexes_count = len(indexes['G'])
B_indexes_count = len(indexes['B'])
indexes_count = {'R': R_indexes_count,
                 'G': G_indexes_count, 'B': B_indexes_count}
# 短いやつを使うとかする？,
if R_indexes_count <= G_indexes_count and R_indexes_count <= B_indexes_count:
    min_type = 'R'
    if G_indexes_count <= B_indexes_count:
        second_min_type = 'G'
        last_type = 'B'
    else:
        second_min_type = 'B'
        last_type = 'G'
elif G_indexes_count <= R_indexes_count and G_indexes_count <= B_indexes_count:
    min_type = 'G'
    if R_indexes_count <= B_indexes_count:
        second_min_type = 'R'
        last_type = 'B'
    else:
        second_min_type = 'B'
        last_type = 'R'
else:
    min_type = 'B'
    if G_indexes_count <= R_indexes_count:
        second_min_type = 'G'
        last_type = 'R'
    else:
        second_min_type = 'R'
        last_type = 'G'

# print(min_type, second_min_type, last_type)
for R_index in indexes[min_type]:
    for G_index in indexes[second_min_type]:
        middle_index = (R_index + G_index) / 2
        remove_conut = 0
        if middle_index != R_index and middle_index != G_index:
            if middle_index in indexes[last_type]:
                remove_conut += 1
        div = abs(G_index - R_index)
        if G_index < R_index:
            if G_index - div in indexes[last_type]:
                remove_conut += 1
            if R_index + div in indexes[last_type]:
                remove_conut += 1
        else:
            if G_index + div in indexes[last_type]:
                remove_conut += 1
            if R_index - div in indexes[last_type]:
                remove_conut += 1
        count += (indexes_count[last_type] - remove_conut)

print(count)


### FIXED CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for i in range(N):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1
ans = r * g * b

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        x = j + j - i
        if S[i] != S[j] and x <= N - 1:
            if S[i] != S[x] and S[x] != S[j]:
                ans -= 1

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

class Tree:
    value=0
    def __init__(self,position):
        self.position = position
        self.kid = set()
        self.value = 0

    def add_kid(self,it):
        self.kid.add(it)

    def add_val(self,val):
        self.value += val

    def calc(self,val=0):
        self.add_val(val)
        # print("called",len(self.kid))
        for i in self.kid:
            if(not(i.position in serched)):
                serched.add(i.position)
                i.calc(self.value)

    def print_val(self):
        print(self.value,end=" ")

N,Q = [int(x) for x in input().split()]
ki = [Tree(i) for i in range(N)]

for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    ki[a-1].add_kid(ki[b-1])
    ki[b-1].add_kid(ki[a-1])

for i in range(Q):
    position,val = [int(x) for x in input().split()]
    ki[position-1].add_val(val)

serched = set()
serched.add(0)
ki[0].calc()

for i in ki:
    i.print_val()
print()


### FIXED CODE ###

N,Q = [int(x) for x in input().split()]
ki = [0]*N
tr = [[] for _ in range(N)]

for i in range(N-1):
    a,b = [int(x)-1 for x in input().split()]
    tr[a].append(b)
    tr[b].append(a)

for i in range(Q):
    position,val = [int(x) for x in input().split()]
    ki[position-1] += val

stack =[0]
visited = set()
visited.add(0)

while stack:
    i = stack.pop()
    for j in tr[i]:
        if j in visited:
            continue
        visited.add(j)
        ki[j] += ki[i]
        stack.append(j)

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

h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
magic = []
a_max = 0
for i in range(n):
    a, b = map(int, input().split())
    a_max = max(a, a_max)
    magic.append((a, b))

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

x_cost = [[0 for _ in range(N)] for _ in range(1 << N)]
y_cost = [[0 for _ in range(N)] for _ in range(1 << N)]

for bit in range(1 << N):
    for i in range(N):
        x_cost[bit][i] = abs(XYP[i][0])
        y_cost[bit][i] = abs(XYP[i][1])

        for k in range(N):
            if bit & (1 << k):
                x_cost[bit][i] = min(x_cost[bit][i], abs(XYP[i][0] - XYP[k][0]))
                y_cost[bit][i] = min(y_cost[bit][i], abs(XYP[i][1] - XYP[k][1]))

ans = [sys.maxsize for _ in range(N + 1)]

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    for i in range(bit, -1, -1):
        i &= bit
        cost = 0
        for k in range(N):
            if ~(bit & (1 << k)):
                cost += 1 * XYP[k][2] * min(x_cost[i][k], y_cost[bit - i][k])
        ans[cnt] = min(ans[cnt], cost)

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

### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

X = int(readline())

if X <= 599:
    print(8)
elif X <= 799:
    print(7)
elif X <= 999:
    print(6)
elif X <= 1199:
    print(5)
elif X <= 1399:
    print(4)
elif X <= 1599:
    print(3)
elif X <= 1799:
    print(2)
elif X <= 1999:
    print(1)
### BUGGY CODE ###

from sys import stdin

ans = []
temp_array = []
temp_ans = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    N_l = len(N)
    global temp_ans
    global ans
    global temp_array
    for i in range(N_l)[::-1]:
        ans += N[i]
        if i == -N_l+1:
            temp_ans = ans
        if len(temp_ans) != 0:
            temp_ans += [N[i]+s for s in temp_ans if s[0] != N[i] and N[i] not in s]
        ans += temp_array
        temp_ans = ans
        temp_array = []
    return len(ans) % (10**9 + 7)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
import math
import itertools


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# これだと、O(n*n)
"""
temp_ans = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    N_l = len(N)
    global temp_ans
    for i in range(N_l)[::-1]:
        temp_ans += N[i]
        #print(temp_ans)
        for s in temp_ans:
            #print(s)
            if N[i] not in s:
                temp_ans.append(N[i]+s)
    #print(temp_ans)
    return len(temp_ans) % (10**9 + 7)
"""


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    #print(S)
    dic = {}
    c = 0
    for i in range(S)[::-1]:
        if N[i] not in dic:
            dic[N[i]] = 1
            #c += i+1
        else:
            dic[N[i]] += 1

    c = 1
    for key, value in dic.items():
        c *= (value+1)
    c -= 1
    """
    c += 2**len(dic.keys())-1
    #print(c)
    #c += S
    for key, value in dic.items():
        if value > 1:
            #c -= (value-1)
            c += 2**(len(dic.keys()))-1
            #print(c)
    #for key, value in dic.items():
    for key, value in dic.items():
        if value > 1:
            if len(dic.keys()) != S:
                c -= 2**(S-len(dic.keys())-1)
    """
            #print(c)
        #else:
    #c += (S-len(dic.keys()))
    """
    s_N = sorted(N)
    for i in range(S-1):
        if s_N[i] != s_N[i+1]:
            c += 2**(i+2)
    """
    """
    for key, value in dic.items():
        if value > 1:
            c += 2**(len(dic.items())-value)
        else:
            c += 2**(len(dic.items())-value)
    """
    #combinations_count(len(, r)

    return c % (10**9 + 7)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


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

N=int(input())
A=list(map(int,input().split()))
ans=1
for i in range(N):
    ans*=A[i]
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
if 0 in A:
    print(0)
    exit()
for i in range(N):
    ans*=A[i]
    if ans>10**18:
        print(-1)
        exit()
else:
    print(ans)
### BUGGY CODE ###

import bisect

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

for i in range(m):
	max_card, num = list(map(int, input().split() ))

	num_small = bisect.bisect(values, num)
	num_to_change = min(max_card, num_small)

	# sort
	# values = values[num_to_change:num_small] + [num]*num_to_change + values[num_small:]
	del  values[:num_to_change]
	values[num_small - num_to_change : num_small - num_to_change] = [num]*num_to_change

print (sum(values))

### FIXED CODE ###

from operator import itemgetter
n, m = list(map(int, input().split() ))
values = list(map(int, input().split() ))
values.sort()

card_change = [list(map(int, input().split() )) for _ in range(m)]
card_change.sort(key = itemgetter(1))
# 変更後の数をkeyとしてソート

# X枚書き換えるとして、Xを全探索する方針で書いてみる
now = sum(values)
ans = sum(values)
idx = m - 1
for x in range(n):
	now -= values[x]

	card_change[idx][0] -= 1 # 変更可能枚数
	now += card_change[idx][1] # 変更後の値

	if now > ans:
		ans = now

	if card_change[idx][0] == 0:
		idx -= 1
		if idx < 0:
			break

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

a, b, x = map(int, input().split())
cnt = 0
for i in range(a, b + 1):
    if i % x == 0:
        cnt += 1
print(cnt)


### FIXED CODE ###

a,b,x = map(int,input().split())
zenbu = b // x +1
tmp = 0
if a % x == 0:
    tmp += 1
bubun = a // x +1
ans = zenbu - bubun + tmp
print(ans)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
h = [int(input()) for i in range(N)]

h.sort()


divide=[]
for i in range(N-K+1):
    divide.append(max(h[i:i+K])-min(h[i:i+K]))

print(min(divide))

### FIXED CODE ###

N, K = list(map(int, input().split()))
h = [int(input()) for i in range(N)]

h.sort()

print(min(h[i+K-1]-h[i]  for i in range(N-K+1)))
### BUGGY CODE ###

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

ans=0
for i in range(N):
    #print(ans)
    flag='on'
    if ans+i==N:
        break
    for j in range(len(a)):
        if a[j]==i+1:
            break
        elif a[j]==0:
            continue
        elif a[j]==i and flag=='on':
            a[j]=0
            flag='off'
        else:
            a[j]=0
            ans+=1
        #print(a)

if ans==N:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans=0
if min(a)!=1:
    print(-1)
else:
    for i in range(N):
        if a[i]==ans+1:
            ans+=1
    print(N-ans)
### BUGGY CODE ###

import itertools


input()
nums = [int(i) for i in input().split(" ")]
longest = len(bin(max(nums))) - 2
nums_bin = [format(i, "b").zfill(longest) for i in nums]


result = 0
for i in range(1, longest+1):
    one = 0
    zero = 0
    for num_bin in nums_bin:
        if num_bin[-1*i] == "1":
            one += 1
        elif num_bin[-1*i] == "0":
            zero += 1
        else:
            raise Exception()
    result += (2 ** (i-1)) * (one * zero)
print(result % (10 ** 9 + 7))

### FIXED CODE ###

import itertools


N = int(input())
nums = [int(i) for i in input().split(" ")]
longest = len(bin(max(nums))) - 2
nums_bin = [format(i, "b").zfill(longest) for i in nums]


result = 0
for index, numbers in enumerate(zip(*nums_bin)):
    i = longest - index - 1
    zero = numbers.count("0")
    one = N - zero
    result += (2 ** i) * (zero * one)
print(result % (10 ** 9 + 7))
### BUGGY CODE ###

from collections import deque

Y, X = map(int,input().split())
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())
sy,sx = 1,1
gy,gx = Y,X
s = [["#"]*(X+2) for _ in range(Y+2)]
for y in range(Y):
    s[y+1] = list("#"+input()+"#")
inf = Y*X
c = [[inf]*X for _ in range(Y)]
c[sy-1][sx-1] = 0
drs = [(-1,0),(1,0),(0,-1),(0,1)]
q = deque([(sy-1, sx-1)])

while q:
    y,x = q.pop()
    cost = c[y][x]
    for dx,dy in drs:
        x2 = x+dx
        y2 = y+dy
        if s[y2+1][x2+1] == "." and c[y2][x2] > cost:
            c[y2][x2] = cost+1
            q.append((y2,x2))
if c[gy-1][gx-1] == inf:
    print("-1")
else:
    dots = 0
    for s1 in s:
        dots +=s1.count(".")
    print(dots-c[gy-1][gx-1]-1)

### FIXED CODE ###

H, W = map(int,input().split())
c = [["#"]*(W+2) for _ in range(H+2)]
dots = 0
for y in range(H):
    c[y+1] = "#",*list(input()),"#" 
    dots += c[y+1].count(".")
inf = H*W
m = [[inf]*W for _ in range(H)]
m[0][0] = 0
drs = [[-1,0],[1,0],[0,-1],[0,1]]

s = 0
yx = [[1, 1]]
notgoal = True
while notgoal and yx:
    yx2 = []
    s += 1
    for y,x in yx:
        for dy, dx in drs:
            x2 = x+dx
            y2 = y+dy
            if c[y2][x2] == "." and m[y2-1][x2-1] == inf:
                m[y2-1][x2-1] = s
                if (y2,x2) == (H,W):
                    notgoal = False
                else:
                    yx2.append([y2, x2])
    yx = yx2

if notgoal:
    print("-1")
else:
    print(dots-s-1)
### BUGGY CODE ###

from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [tuple(map(int, input().split())) for _ in range(Q)]

ans = 0
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans = max(ans, z)
    z = 0
print(ans)

### FIXED CODE ###

from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = []
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans.append(z)
    z = 0
print(max(ans))
### BUGGY CODE ###

a, b, k = map(int, input().split())

int_list = [i for i in range(a, b+1)]
out_list = sorted(set(int_list[:k] + int_list[-k:])) 

for out_val in out_list:
    print(out_val)

### FIXED CODE ###

a, b, k = map(int, input().split())

lower_list = [i for i in range(a, a + k)]
upper_list = [i for i in range(b, b - k, -1)]
out_list = sorted(set(lower_list + upper_list))

for out_val in out_list:
    if a <= out_val <= b:
        print(out_val)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
aa = [0] * (10 ** 6 + 1)
a.sort()
ans = 0


for i in a:
    for j in range(i, 10 ** 6 + 1, i):
        aa[j] += 1

a = set(a)

for k in a:
    if aa[k] == 1:
        ans += 1


print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (10 ** 6 + 1)
a.sort()
ans = 0


for i in a:
    cnt[i] += 1

a = set(a)

for k in a:
    for l in range(k * 2, (10 ** 6 + 1), k):
        cnt[l] += 1

for m in a:
    if cnt[m] == 1:
        ans += 1
    


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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = map(int,input().split())
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

D = []
for i in range(M):
    b,c = change[i]
    for j in range(b):
        D += [c]

D.sort()
D.reverse()

A.sort()
ans = sum(A)
for i in range(min(len(D),len(A))):
    dif = D[i]-A[i]
    if dif < 0:
        break
    else:
        ans += dif
print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = map(int,input().split())
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

D = []
change = sorted(change,key=lambda x:x[1],reverse=True)
for i in range(M):
    b,c = change[i]
    for j in range(b):
        D += [c]
    if len(D) > N:
        break

A += D
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

N,K=map(int,input().split())
h=[int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N):
  if i != 0:
    res.append(h[i]-h[i-1])
m=10**10
for i in range(N-K+1):
  ans=0
  for j in range(K-1):
    ans+=res[j+i]
  if ans<m:
    m=ans
print(m)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N-K+1):
  res.append(h[K+i-1]-h[i])
print(min(res))