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

N = int(input())
S = input()

ans = 0
tmp = [0 for _ in range(10)]
for i in range(len(S)):
    tmp[int(S[i])] += 1

for i in range(1000):
    flag = True

    if i < 10:
        dic = {"0": 2}
    elif i < 100:
        dic = {"0": 1}
    else:
        dic = {}
    for j in range(len(str(i))):
        if str(i)[j] in dic:
            dic[str(i)[j]] += 1
        else:
            dic[str(i)[j]] = 1

    for k, v in dic.items():
        if dic[k] > tmp[int(k)]:
            flag = False
            break

    if flag:
        if i < 10:
            tmp_i = "00" + str(i)
        elif i < 100:
            tmp_i = "0" + str(i)
        else:
            tmp_i = str(i)
        t = 0
        for j in range(len(S)):
            if tmp_i[t] == S[j]:
                t += 1
            if t == 3:
                ans += 1
                break

print(ans)



### FIXED CODE ###

N = int(input())
S = input()

ans = 0
tmp = [0 for _ in range(10)]
for i in range(len(S)):
    tmp[int(S[i])] += 1

for i in range(1000):
    flag = True

    if i < 10:
        dic = {"0": 2}
    elif i < 100:
        dic = {"0": 1}
    else:
        dic = {}
    for j in range(len(str(i))):
        if str(i)[j] in dic:
            dic[str(i)[j]] += 1
        else:
            dic[str(i)[j]] = 1

    for k, v in dic.items():
        if dic[k] > tmp[int(k)]:
            flag = False
            break

    if flag:
        if i < 10:
            tmp_i = "00" + str(i)
        elif i < 100:
            tmp_i = "0" + str(i)
        else:
            tmp_i = str(i)
        t = 0
        for j in range(len(S)):
            if tmp_i[t] == S[j]:
                t += 1
            if t == 3:
                ans += 1
                break

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

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z and z<=k:
            if x+y+z == s:
                cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z and z<=k:
          cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
n1 = n + 1
d = [inf] * (n1 * n1)
for i in range(n1):
    d[i * n1 + i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b * n1 + a] = c
for k in range(1, n+1):
    for i in range(1, n+1):
        d = d
        for j in range(i+1, n+1):
            d[i * n1 + j] = d[j * n1 + i] = min(
                d[i * n1 + j],
                d[i * n1 + k] + d[k * n1 + j])
s = inf
for q in itertools.permutations(range(r)):
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]] * n1 + rs[q[i+1]]]
    if s > t:
        s = t
print(s)


### FIXED CODE ###

from itertools import product, permutations


def warshall_floyd(d):
    # d        : nxn adjacent matrix
    for k, i, j in product(range(n), repeat=3):
        if d[i][j] > d[i][k] + d[k][j]:
            d[i][j] = d[i][k] + d[k][j]


INF = float("inf")
n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

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

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
D = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for i, (v, u) in enumerate(VU):
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

edges = {}
colors = [None] * N
for v in argsort(D):
    d = D[v]
    if colors[v] is not None:
        continue
    for u in graph[v]:
        if colors[u] is not None:
            edges[v, u] = d
            colors[v] = not colors[u]
            break
        if D[u] == d:
            edges[v, u] = d
            colors[v] = True
            colors[u] = False
            break
    if colors[u] is None:
        print(-1)
        exit()
S = ''
for c in colors:
    S += 'B' if c else 'W'
ans = []
for v, u in VU:
    v -= 1
    u -= 1
    if (v, u) in edges:
        ans.append(edges[v, u])
    elif (u, v) in edges:
        ans.append(edges[u, v])
    else:
        ans.append(10 ** 9)

print(S)
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
D = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for i, (v, u) in enumerate(VU):
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

edges = {}
colors = [None] * N
for v in argsort(D):
    d = D[v]
    if colors[v] is not None:
        continue
    for u in graph[v]:
        if colors[u] is not None:
            edges[v, u] = d
            colors[v] = not colors[u]
            break
        if D[u] == d:
            edges[v, u] = d
            colors[v] = True
            colors[u] = False
            break
    if colors[u] is None:
        print(-1)
        exit()
S = ''
for c in colors:
    S += 'B' if c else 'W'
ans = []
for v, u in VU:
    v -= 1
    u -= 1
    if (v, u) in edges:
        ans.append(edges[v, u])
    elif (u, v) in edges:
        ans.append(edges[u, v])
    else:
        ans.append(10 ** 9)

print(S)
print(*ans, sep='\n')
### BUGGY CODE ###



cache = {0: 1, 1: 1, 2: 2}
combo_cache = {}


def prepare_cache():
    val = 1
    for i in range(1, 10000):
        val *= i
        cache[i] = val

def permutation(n):
    if n in cache:
        return cache[n]

    ret = n
    for i in range(n-1, 0, -1):
        if i in cache:
            ret *= cache[i]
            cache[n] = ret
            return ret

        ret *= i
    return ret


def combo(n, r):
    key = str(n) + "-" + str(r)
    if key in combo_cache:
        return combo_cache[key]

    x = permutation(n)
    y = permutation(n-r)
    z = permutation(r)
    combo_cache[key] = int(x // (y * z))
    return combo_cache[key]


count = int(input())
li = list(map(int, input().split()))
#
# data = open("input.txt", "r")
# l = data.read()
# li = list(map(int, l.split(" ")))

prepare_cache()

sli = sorted(li)

pair_a = 0
pair_b = 0
current_max = 0

i = sli[len(sli) - 1]

for j in range(0, len(sli) - 1):
    val = combo(i, sli[j])
    # print(str(sli[i]) + ", " + str(sli[j]) + ", " + str(val))
    if val > current_max:
        current_max = val
        pair_a = i
        pair_b = sli[j]

print(str(pair_a) + " " + str(pair_b))


### FIXED CODE ###

count = int(input())
li = list(map(int, input().split()))

sli = sorted(li)

pair_a = sli[len(sli) - 1]
pair_b = 0
current_max = 0

i = sli[len(sli) - 1]

diff = 10**9
for j in range(0, len(sli) - 1):
    h = pair_a / 2
    if abs(h - sli[j]) < diff:
        diff = abs(h - sli[j])
        pair_b = sli[j]

print(str(pair_a) + " " + str(pair_b))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
Maze = [list(input()) for _ in range(H)]
ans = 0
sy = 0
while sy < H:
  sx = 0
  while sx < W:
    if Maze[sy][sx] == ".":
      M_cnt = 0
      q = deque()
      memo = [[False]*(W) for _ in range((H))]
      q.append([[sy, sx],0])
      while q:
        cur, cnt = q.popleft()
        cy, cx = cur
        memo[cy][cx] = True
        M_cnt = max(M_cnt, cnt)
        for ny, nx in zip((cy, cy, cy+1, cy-1) , (cx+1, cx-1, cx, cx)):
          if ny >= 0 and ny < H and nx >= 0 and nx < W and Maze[ny][nx] == "." and not memo[ny][nx]:
            q.append([[ny, nx],cnt+1])
      ans = max(ans, M_cnt)
    sx += 1
  sy += 1
print(ans)

### FIXED CODE ###

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


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = input()

def calculate(n, s):
    arr = list(s)

    rNum = arr.count("R")
    gNum = arr.count("G")
    bNum = arr.count("B")


    sum = 0

    for i in range(n):
        for j in range(i + 1, n):
            start = i
            middle = j
            end = i + (j - i) * 2
            if end > n - 1:
                continue

            dict = {"R": False, "G": False, "B": False}
            dict.__setitem__(arr[start], True)
            dict.__setitem__(arr[middle], True)
            dict.__setitem__(arr[end], True)
            dictArr = np.array(list(dict.values()))
            if np.sum(dictArr == True) == 3:
                sum = sum + 1

    print(rNum*gNum*bNum - sum)


calculate(N, S)


### FIXED CODE ###

import math
N = int(input())
S = input()

# N = 39
# S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

def calculate(n, s):
    arr = list(s)

    rNum = arr.count("R")
    gNum = arr.count("G")
    bNum = arr.count("B")

    sum = 0

    for step in range(1,math.ceil(n / 2) + 1):
        for i in range(n - 2*step):
            s = "".join([arr[i],arr[i+step],arr[i+step*2]])
            if s == "RGB" or s == "RBG" or s == "BGR" or s == "BRG" or s == "GBR" or s == "GRB":
                sum = sum + 1


    print(rNum*gNum*bNum - sum)



calculate(N, S)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
s = 0
for i in range(N):
    s += A[i]
    S.append(s)
ans = 0
for i in range(N):
    x = S.pop(0)
    if x == 0:
        ans += 1
    ans += S.count(x)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
s = 0
for i in range(N):
    s += A[i]
    S.append(s)
ans = 0
S.sort()
x = S[0]
j = 1
if x == 0:
    ans += 1
for i in range(1,N):
    y = S[i]
    if y == 0:
        ans += 1
    if x == y:
        ans += j
        j += 1
    else:
        x = y
        j = 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

def calc(x,y):
    i = len(x)
    j = len(y)
    if d[i][j]:
        return d[i][j]
    else:
        if i == 1:
            if x in y:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        elif j == 1:
            if y in x:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        else:
            if x[-1] == y[-1]:
                tmp = max(calc(x[:-1],y[:-1])+1,calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
            else:
                tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[None for _ in range(len(y)+1)] for _ in range(len(x)+1)]
    print(calc(x,y))


### FIXED CODE ###

def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))
### BUGGY CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: #すでに余裕をもって到達済み
        break
      reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
      Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)
                 
  
  

### FIXED CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: #すでに余裕をもって到達済み
        break
      if reach[x][y]+1 < reach[nx][ny]:
        reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
        Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)
### BUGGY CODE ###

import numpy as np
h, w, a, b = map(int, input().split())
m = np.zeros((h,w))
m[0:b,a:] = 1
m[b:,0:a] = 1
for j in range(h):
    print(''.join(m.astype(int).astype(str)[j].tolist()))

### FIXED CODE ###

import numpy as np
h, w, a, b = map(int, input().split())
m = np.zeros((h,w),np.int8)
m[:b,a:] = 1
m[b:,:a] = 1
print('\n'.join(''.join(row) for row in m.astype(str)))
### BUGGY CODE ###

def f():
    n=int(input())

    if n==1:
        print("Yes")
        print(2)
        print(1,1)
        print(1,1)
        exit()
    a=1
    while True:
        t=a*(a-1)//2
        if t>n:
            print("No")
            exit()
        if t==n:
            print("Yes")
            break
        a+=1
    print(a)
    s=set(range(1,1+n))
    l=[0]*(n+1)
    ans=[set()]

    for i in range(a):
        ll=set()
        for j in ans[:i+1]:
            for p in s&j:
                if p not in ll:
                    ll.add(p)
                    if l[p]==1:
                        s.remove(p)
                    else:
                        l[p]+=1
                    break

        for p in s:
            if len(ll)>=n*2//a:
                break
            else:
                if l[p]==0:
                    ll.add(p)
                    l[p]+=1

        ans.append(ll)
        q=[n*2//a]+list(ll)
        print(*q)

f()


### FIXED CODE ###

def main():
    n=int(input())
    m=int((2*n)**0.5)
    if m*(m+1)==n*2:
        print("Yes")
        m+=1
        print(m)
    else:
        print("No")
        exit()
    
    ans=[[m-1] for i in range(m)]
    c=1
    for i in range(m):
        for j in range(i+1,m):
            ans[i].append(c)
            ans[j].append(c)
            c+=1
    for i in ans:
        print(*i)


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

import sys
input=sys.stdin.readline
import heapq
import math
def main():
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  d=list(map(int,input().split()))
  if b>=sum(c):
    print(0)
  else:
    c.sort()
    d.sort(reverse=True)
    e=[c[i]*d[i] for i in range(a)]
    f=[]
    for i in range(a):
      heapq.heappush(f,-e[i])
    k=0
    while k<b or f[0]==0:
      x=-heapq.heappop(f)
      y=e.index(x)
      z=min(b-k,(x+f[0])//d[y]+1)
      k+=z
      c[y]=c[y]-z
      e[y]=c[y]*d[y]
      heapq.heappush(f,-e[y])
    print(-f[0])
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

import math
a,b=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
c.sort()
d.sort(reverse=True)
e=[0 for i in range(a)]
for i in range(a):
  e[i]=c[i]*d[i]
def s(e,x):
  k=0
  for i in range(a):
    if e[i]<x:
      continue
    else:
      k+=math.ceil((e[i]-x)/d[i])
  if k>b:
    return False
  else:
    return True
    
left=0
right=max(e)
while left!=right:
  mid=(left+right)//2
  if s(e,mid):
    right=mid
  else:
    left=mid+1
print(left)
### BUGGY CODE ###

def main():
    n,a,b = map(int,input().split())
    tmp = 1
    ans = 0
    for n,r in zip(range(n,-1,-1),range(1,n+1)):
        tmp = tmp*n//r
        if r != a and r != b:
            ans += tmp
    print(ans%(10**9+7))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def mod_comb(n,k,mod):
    result = 1
    for i in range(n-k+1,n+1):
        result *= i
        result %= mod
    for i in range(1,k+1):
        result *= pow(i,mod-2,mod)
        result %= mod
    return result


def main():
    n,a,b = map(int,input().split())
    mod = 10**9+7
    ans = pow(2,n,mod)-1
    ans = (ans - mod_comb(n,a,mod))%mod
    ans = (ans - mod_comb(n,b,mod))%mod
    print(ans)

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

cnt=0
k,s=map(int,input().split())
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l==s:
                cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        if 0<=s-x-y<=k:
            ans+=1
print(ans)
### BUGGY CODE ###


def main():
    n = int(input())
    a = list(map(int,input().split()))
    temp = 1
    for n in a:
        temp *= n
    if temp > (10 ** 18):
        temp = -1
    print(temp)

if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    n = int(input())
    a = list(map(int,input().split()))
    temp = 1
    if 0 in a:
        temp = 0

    for n in a:
        if temp == -1:
            break
        temp *= n
        if temp > 10 ** 18:
            temp = -1
            break
    print(temp)

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

import itertools
n = int(input())
l = list(map(int, input().split()))
total = 0
mod = 1000000007
ans = 0
for a,b in itertools.combinations(l, 2):
    total += ((a % mod) * (b % mod)) % mod
print(total % mod)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
mod = 1000000007
q = sum(l)
ans = 0
for i in range(len(l)):
    q -= l[i]
    ans += l[i] * q % mod
print(ans % mod)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
li = na()
list.sort(li)
ls = []
if len(li) - 1 < n - 1:
    print(0)
else:
    for i in range(len(li) - 1):
        ls.append(li[i + 1] - li[i])
    for j in range(n - 1):
        ls.remove(max(ls))
    print(sum(ls))

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
li = na()
ls = []
list.sort(li)
for i in range(len(li) - 1):
    ls.append(li[i + 1] - li[i])
ls = sorted(ls, reverse=True)
print(sum(ls[n-1:]))
### BUGGY CODE ###


from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = []
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            cc.append(dfs(fr,v,temp,visited))
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    for component in cc:
        if i in component:
            aa = len(component) - len(component & fr[i]) - len(component & bl[i]) - 1
            ans.append(aa)
print(*ans)

### FIXED CODE ###


from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = [0]*n
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            for i in dfs(fr,v,temp,visited):
                cc[i] = dfs(fr,v,temp,visited)
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    aa = len(cc[i]) - len(cc[i] & fr[i]) - len(cc[i] & bl[i]) - 1
    ans.append(aa)
print(*ans)