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

"""
A - Limited Insertion
"""


def solve():
    N = int(input())
    b = list(map(int, input().split()))
    ans = make_list(b, 0, [])

    if ans == -1:
        print(ans)
    else:
        ans = list(reversed(ans))
        ans = [str(i) for i in ans]
        print(' '.join(ans))


def make_list(b: list, x: int, ans: list) -> list:
    re = -1
    # print('try {}'.format(x))
    # print(b)

    if len(b) == 0:
        return ans

    for i, element in enumerate(b, 1):
        if i == element:
            b_c = b.copy()
            ans_c = ans.copy()
            ans_c.append(b_c[i - 1])
            b_c.remove(element)  # 除去対象は自分より前に同じ要素が存在しない
            # print('match element {}'.format(element))
            # print(ans)
            tmp = make_list(b_c, x + 1, ans_c)
            if tmp != -1:
                re = tmp
                break
    # print('return {} is '.format(x), re)
    return re


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
A - Limited Insertion
"""


def solve():
    N = int(input())
    b = list(map(int, input().split()))
    ans = make_list(b, 0, [])

    if ans == -1:
        print(ans)
    else:
        for a in list(reversed(ans)):
            print(a)
        # ans = list(reversed(ans))
        # ans = [str(i) for i in ans]
        # print(' '.join(ans))


def make_list(b: list, x: int, ans: list):
    re = -1
    # print('try {}'.format(x))
    # print(b)

    if len(b) == 0:
        return ans

    if check_list(b) is False:
        return re

    for i, element in enumerate(b, 1):
        if i == element:
            b_c = b.copy()
            ans_c = ans.copy()
            ans_c.append(b_c[i - 1])
            b_c.remove(element)  # 除去対象は自分より前に同じ要素が存在しない
            # print('match element {}'.format(element))
            # print(ans)
            tmp = make_list(b_c, x + 1, ans_c)
            if tmp != -1:
                re = tmp
                break
    # print('return {} is '.format(x), re)
    return re


def check_list(b):
    re = True
    for i, element in enumerate(b, 1):
        if i < element:
            re = False
            break
    return re


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

from math import gcd

k = int(input())

ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            temp = gcd(gcd(a, b), c)
            ans += temp
print(ans)

### FIXED CODE ###

from math import gcd

k = int(input())

r = range(1, k + 1)
ans = sum([gcd(gcd(a, b), c) for a in r for b in r for c in r])
print(ans)
### BUGGY CODE ###

import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=['' for i in range(0,N)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[i]=t[0]

for i in range(1,M):
    x=t[i]
    if index[x]:
        for j in range(N-1,index[x][0]-1,-1):
            next=index[x][bisect.bisect_right(index[x],j)-1]-1
            if next>=0:
                if len(dp[j])<1+len(dp[next]):
                    dp[j]=dp[next]+t[i]
            else:
                if dp[j]=='':
                    dp[j]=t[i]

print(dp[N-1])

### FIXED CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

ans=[]
i=N
j=M
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
for i in range(n):
    a = x[:i] + x[i+1:]
    a.sort(reverse=True)
    print(a[n//2-1])

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
sx = sorted(x)

for i in range(n):
    if x[i] < sx[n//2]:
        print(sx[n//2])
    else:
        print(sx[n//2-1])
### BUGGY CODE ###

def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y) 

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

def isPrime(n):
  if n <= 2:
    return True
  for p in range(2, n):
      if n % p == 0:
        return False
  return True
    
a,b = map(int,input().split())
gcd = gcd(a,b)
yks = make_divisors(gcd)
ans = 0
for i in yks:
  if isPrime(i):
    ans +=1
print(ans)

### FIXED CODE ###

def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y) 

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

def isPrime(n):
  if n <= 2:
    return True
  m = int((n**0.5)//1 + 1)
  for p in range(2, m):
      if n % p == 0:
        return False
  return True
    
a,b = map(int,input().split())
gcd = gcd(a,b)
yks = make_divisors(gcd)
ans = 0
for i in yks:
  if isPrime(i):
    ans +=1
print(ans)
### BUGGY CODE ###

N = int(raw_input())

upper = list()
lower = list()

right_end = 0
search_end = 0 
while True:
    if right_end == 0:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join(upper + [q[0]])
            print "".join(lower + [q[1]])

            r = raw_input()
            if r == 'T':
                upper.append(q[0])
                lower.append(q[1])
                if len(upper) == N:
                    search_end = 1
                break
            if r == 'F' and q == ['#', '#']:
                right_end = 1
    else:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join([q[0]] + upper)
            print "".join([q[1]] + lower)
            
            r = raw_input()
            if r == 'T':
                upper.insert(0,q[0])
                lower.insert(0,q[1])
                if len(upper) == N:
                    search_end = 1
                break
    if search_end == 1:
        break




### FIXED CODE ###

import sys
N = int(raw_input())
upper = list()
lower = list()

right_end = 0
search_end = 0 
while True:
    if right_end == 0:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join(upper + [q[0]])
            print "".join(lower + [q[1]])
            sys.stdout.flush()

            r = raw_input()
            if r == 'T':
                upper.append(q[0])
                lower.append(q[1])
                break
            elif r == 'end':
                search_end = 1
                break
            if r == 'F' and q == ['#', '#']:
                right_end = 1
    else:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join([q[0]] + upper)
            print "".join([q[1]] + lower)
            sys.stdout.flush()
            
            r = raw_input()
            if r == 'T':
                upper.insert(0,q[0])
                lower.insert(0,q[1])
                break
            elif r == 'end':
                search_end = 1
                break
    if search_end == 1:
        break
### BUGGY CODE ###

def main():
    N, W = list(map(int, input().split(' ')))
    items = [list(map(int, input().split(' '))) for _ in range(N)]
    dp = [[0 for _ in range(W + 1)] for _ in range(N)]
    for w in range(items[0][0], W + 1):
        dp[0][w] = items[0][1]
    for n in range(1, N):
        weight, value = items[n]
        for w in range(W + 1):
            if w - weight >= 0:
                dp[n][w] = max([dp[n - 1][w], value + dp[n - 1][w - weight]])
            else:
                dp[n][w] = dp[n - 1][w]
    print(dp[N - 1][W])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


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

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+1)]

DP[0] = 0

for h in range(H+1):
    for j, magic in enumerate(MAGICS):
        (damage, mp) = magic
        DP[h] = min(DP[max(h - damage, 0)]+mp, DP[h])

print(DP[H])


### FIXED CODE ###

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])
### BUGGY CODE ###

import sys
from collections import Counter
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    a, b, c = count[1], count[2], count[3]
    
    memo = dict()
    
    def dp(a, b, c):
        if (a, b, c) in memo:
            return memo[(a, b, c)]
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        res = N
        res += a*dp(a-1, b, c)
        res += b*dp(a+1, b-1, c)
        res += c*dp(a, b+1, c-1)
        res /= a+b+c
        
        memo[(a, b, c)] = res
        return res
    
    ans = dp(a, b, c)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline


N = int(input())
memo = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

def dp(a, b, c):
    if a == b == c == 0: return 0
    if memo[a][b][c] != -1:
        return memo[a][b][c]
    
    res = N
    if a > 0: res += a*dp(a-1, b, c)
    if b > 0: res += b*dp(a+1, b-1, c)
    if c > 0: res += c*dp(a, b+1, c-1)
    res /= a+b+c
    
    memo[a][b][c] = res
    return res

def main():
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]

    
    ans = dp(x, y, z)
    
    print(ans)
        

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

n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1 and i not in lst:
    DP[i]=1
  elif i==1 and i in lst:
    DP[i]=1
    temp=i+1
  else:
    if i-1 not in lst and i-2 not in lst:
      DP[i]+=DP[i-1]+DP[i-2]
    elif i-1 not in lst and i-2 in lst:
      DP[i]+=DP[i-1]
    elif i-1 in lst and i-2 not in lst:
      DP[i]+=DP[i-2]
    else:
      break;
print(DP[n]%1000000007)

### FIXED CODE ###

N,M=map(int,input().split())
br=set([int(input()) for _ in range(M)])
dp=[0]*(N+1)
dp[0]=1
if not 1 in br:
    dp[1]=1
for i in range(2,N+1):
    if not i in br:
        dp[i]+=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])
### BUGGY CODE ###

import fractions

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

lcm = a[0]
for i in a:
    lcm = lcm * i / fractions.gcd(lcm, i)

ans = 0
for i in a:
    ans += (lcm-1) % i
print(int(ans))


### FIXED CODE ###

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

ans = 0
for i in a:
    ans += i - 1
print(ans)
### BUGGY CODE ###

N = int(input())
str_list = []
for i in range(N):
  str_dict = {}
  for j in input():
    if j in str_dict:
      str_dict[j] += 1
    else:
      str_dict[j] = 1
  str_list.append(str_dict)
  
count = 0
for i in range(N):
  for j in range(i+1, N):
    if str_list[i] == str_list[j]:
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
str_list = {}
for i in range(N):
  str_dict = {}
  for j in input():
    if j in str_dict:
      str_dict[j] += 1
    else:
      str_dict[j] = 1
  key = "".join([str(k)+str(v) for k, v in sorted(str_dict.items(), key=lambda x:x[0])])
  if key in str_list:
    str_list[key] += 1
  else:
    str_list[key] = 1
  
result = sum([i*(i-1)//2 for i in str_list.values()])
print(result)
### BUGGY CODE ###

from collections import Counter
n = int(input())
lst = [Counter(input()) for i in range(n)]
#lst2 = 1#Counter(lst)
#for i in len(lst):
#  print(i.values)
cnt = 0
for i in range(len(lst)-1):
  for j in range(i+1,len(lst)):
    #print(0)
    if lst[i]==lst[j]:
      cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter
#from itertools import combinations
n = int(input())
lst = ["".join(sorted(list(input()))) for i in range(n)]
#lst2 = 1#Counter(lst)
#for i in len(lst):
#  print(i.values)


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

#print(cmb(4,2),0,0,0)
cnt = 0
for i in Counter(lst).values():
  if i == 1:
    continue
  cnt += cmb(i, 2)
"""
for i in range(len(lst)-1):
  for j in range(i+1,len(lst)):
    #print(0)
    if lst[i]==lst[j]:
      cnt += 1
"""
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%(10 ** 9 + 7))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
l = [1] * (n+1)
for j in a:
  l[j] = 0
x = 10 ** 9 + 7
if m > n // 2:
  print(0)
else:
  dp = [0] * (n+1)
  dp[0] = 1
  if 1 not in a:
    dp[1] = 1
  for i in range(2, n+1):
    if l[i]:
      dp[i] = (dp[i-1] + dp[i-2]) % x
  print(dp[-1])
### BUGGY CODE ###

p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    for i in xrange(l, r + 1):
        if i & 1:
            if p[i] and p[(i + 1) / 2]:
                c += 1
    print c


### FIXED CODE ###

p = [True] * 100020
for x in xrange(2, int(100020 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100020):
            if y * x >= 100020:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100020):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]
### BUGGY CODE ###

from collections import defaultdict
n,q = map(int,input().split())
d = defaultdict(list)
dp = defaultdict(int)
ep = [0] * n
for i in range(n-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)
for i in range(q):
    ta,tb = map(int,input().split())
    dp[ta-1] +=tb
ep[0]+=1
l = []
l.append(0)
while l:
    t = l.pop()
    for i in d[t]:
        if ep[i] == 0:
            dp[i] += dp[t]
            ep[i]+=1
            l.append(i)
ans = []
for i in dp:
    ans.append(dp[i])
print(*ans)

### FIXED CODE ###

from collections import defaultdict
from collections import deque
n,q = map(int,input().split())
d = defaultdict(list)
dp = [0] * n
ep = [0] * n
for i in range(n-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)
for i in range(q):
    ta,tb = map(int,input().split())
    dp[ta-1] +=tb
ep[0]+=1
l = deque()
l.append(0)
used = [False] * n
while l:
    t = l.pop()
    used[t] = True
    for i in d[t]:
        if not used[i]:
            dp[i] += dp[t]
            l.append(i)
print(*dp)
### BUGGY CODE ###

N = int(input())
AS = input().split()
for i in AS:
    i = int(i)
abs_list = []
for i in range (-int(max(AS))-1, int(max(AS)) + 1):
    counter = 0
    for j in range (1,N+1):
        counter += abs(int(AS[j-1]) - i - j)
    abs_list.append(counter)
print(min(abs_list))

### FIXED CODE ###

N = int(input())
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for j in range(1,N+1)]
BS_s = BS.sort()
b = BS[N//2]
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print (int(min(result_a,result_b,result_c)))
### BUGGY CODE ###

N = int(input())
A = list(enumerate(list(map(int, input().split()))))
count = 0
B = sorted(A,key=lambda x:x[1])
for i in range(2,N):
    if B[0][1] + B[1][1] > i:
        continue
    elif B[-1][1] + B[-2][1] < i:
        break
    else:
        for j in range(N-1):
            broke = False
            c = B[j][1]
            if c >= i:
                break
            else:
                for k in range(1,N-j):
                    d = B[j+k][1]
                    e = c + d
                    if e > i:
                        break
                    elif e == i:
                        if abs(B[j][0]-B[j+k][0]) == e:
                            count += 1
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
b = Counter([x[0]+x[1]+1 for x in A])
c = Counter([x[0]-x[1]+1 for x in A])
count = 0
for x in b.items():
    count += x[1] * c[x[0]]
print(count)
### BUGGY CODE ###

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

P_before = 1
for k in range(K):
    P_before = P_before*A[k]
    
P_before


for i in range(K,N):
    P = P_before*A[i]//A[i-K]
    
    if P > P_before:
        print('Yes')
    else:
        print('No')
    
    P_before = P

### FIXED CODE ###

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

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

s = input()
num = len(s)
l = []
from collections import deque
l = deque(l)   # deque オブジェクトを取得

for _ in range(1, 20190000):
    if _%2019 == 0:
        l.append(_)
l = set(l)
#print(l)

def aaa(s, num):
    x = 0
    for i in range(4,num+1):
        for j in range(num - i + 1):
            if int(s[j:j+i]) in l:
                x += 1
    print(x)

aaa(s, num)

### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

import sys
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs += [(s,1,x), (t,0,x)]
    tmp.add(x)
for _ in range(Q):
    qs.append(int(input()))

xs.sort()

h=set()
qi = 0
q = qs[qi]
for t,r,x in xs:
    if q < t:
        if h:
            c = min(h)
        else:
            c = -1
        while True:
            if q < t:
                print(c)
                Q-=1
                if Q:
                    qi += 1
                    q = qs[qi]
                    continue
                sys.exit()
            break
    if r:
        h.add(x)
    else:
        h.remove(x)
print("-1\n"*Q)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

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

for i in range(M):
  tmp = max(As)
  As.remove(tmp)
  tmp = tmp // 2
  As.append(tmp)
  
print(sum(As))


### FIXED CODE ###

N, M = map(int, input().split())
import heapq

As = list(map(lambda x : -1 * int(x), input().split()))

heapq.heapify(As)

for i in range(M):
  tmp = heapq.heappop(As)
  tmp = (-1 * tmp) // 2 * (-1) 
  heapq.heappush(As, tmp)
  
print(-1 * sum(As))
### BUGGY CODE ###

#C-117
n, m = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
if n >= m:
  print(0)
elif n == 1:
  print(max(x) - min(x))
else:
  x.sort()
  x_diff = []
  for mi in range(m-1):
    x_diff.append(x[mi+1]-x[mi])
  #print(x_diff)
  split_list = []
  for ni in range(n-1):
    split_idx = x_diff.index(max(x_diff))
    split_list.append(split_idx)
    x_diff[split_idx] = 0
  split_list.sort()
  #print(split_list)
  #print(x)
  ans = 0
  ans += x[split_list[0]] - x[0]
  #print("ans",ans)
  for ni in range(n-2):
    l = split_list[ni]+1
    r = split_list[ni+1]
    ans += x[r] - x[l]
    #print("ans",ans)
  ans += x[-1] - x[split_list[-1]+1]
  print(ans)


### FIXED CODE ###

#C-117
n, m = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
if n >= m:
  print(0)
elif n == 1:
  print(max(x) - min(x))
else:
  x.sort()
  x_diff = []
  for mi in range(m-1):
    x_diff.append([x[mi+1]-x[mi], mi])
  #print(x_diff)
  x_diff.sort(reverse = True)
  #print(x_diff)
  split_list = []
  for ni in range(n-1):
    split_idx = x_diff[ni][1]
    split_list.append(split_idx)
  split_list.sort()
  #print(split_list)
  #print(x)
  ans = 0
  ans += x[split_list[0]] - x[0]
  #print("ans",ans)
  for ni in range(n-2):
    l = split_list[ni]+1
    r = split_list[ni+1]
    ans += x[r] - x[l]
    #print("ans",ans)
  ans += x[-1] - x[split_list[-1]+1]
  print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n):
    ans += i
print(ans)


### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    exit()
ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)