Polycarp is practicing his problem solving skill. He has a list of $n$ problems with difficulties $a_1, a_2, \dots, a_n$, respectively. His plan is to practice for exactly $k$ days. Each day he has to solve at least one problem from his list. Polycarp solves the problems in the order they are given in his list, he cannot skip any problem from his list. He has to solve all $n$ problems in exactly $k$ days.

Thus, each day Polycarp solves a contiguous sequence of (consecutive) problems from the start of the list. He can't skip problems or solve them multiple times. As a result, in $k$ days he will solve all the $n$ problems.

The profit of the $j$-th day of Polycarp's practice is the maximum among all the difficulties of problems Polycarp solves during the $j$-th day (i.e. if he solves problems with indices from $l$ to $r$ during a day, then the profit of the day is $\max\limits_{l \le i \le r}a_i$). The total profit of his practice is the sum of the profits over all $k$ days of his practice.

You want to help Polycarp to get the maximum possible total profit over all valid ways to solve problems. Your task is to distribute all $n$ problems between $k$ days satisfying the conditions above in such a way, that the total profit is maximum.

For example, if $n = 8, k = 3$ and $a = [5, 4, 2, 6, 5, 1, 9, 2]$, one of the possible distributions with maximum total profit is: $[5, 4, 2], [6, 5], [1, 9, 2]$. Here the total profit equals $5 + 6 + 9 = 20$.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the number of problems and the number of days, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2000$) — difficulties of problems in Polycarp's list, in the order they are placed in the list (i.e. in the order Polycarp will solve them).


-----Output-----

In the first line of the output print the maximum possible total profit.

In the second line print exactly $k$ positive integers $t_1, t_2, \dots, t_k$ ($t_1 + t_2 + \dots + t_k$ must equal $n$), where $t_j$ means the number of problems Polycarp will solve during the $j$-th day in order to achieve the maximum possible total profit of his practice.

If there are many possible answers, you may print any of them.


-----Examples-----
Input
8 3
5 4 2 6 5 1 9 2

Output
20
3 2 3
Input
5 1
1 1 1 1 1

Output
1
5

Input
4 2
1 2000 2000 2

Output
4000
2 2



-----Note-----

The first example is described in the problem statement.

In the second example there is only one possible distribution.

In the third example the best answer is to distribute problems in the following way: $[1, 2000], [2000, 2]$. The total profit of this distribution is $2000 + 2000 = 4000$.

Difficulty: EASY
Tags: Sorting

Implementation

Greedy algorithms
Skill types: Sorting

Greedy algorithms
Expected Time Complexity: O(NLOG(N))

Starter code:

Solutions:
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ind = [n + 1]
su = 0
for i in range(k):
	ma = max(a)
	su += ma
	index = a.index(ma)
	ind.append(index + 1)
	a[index] = 0
ind.sort()
print(su)
if k == 1:
	print(n)
	exit()
print(ind[0], end=' ')
for i in range(1, k):
	if i == 1:
		print(ind[2] - ind[0] - 1, end=' ')
	else:
		print(ind[i + 1] - ind[i], end=' ')


from collections import deque as de
import math
from collections import Counter as cnt

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
l = sorted(a, reverse=True)
dic = {}
totalprofit = 0
for i in range(k):
	totalprofit += l[i]
	if l[i] in dic:
		dic[l[i]] += 1
	else:
		dic[l[i]] = 1
ans = []
count = 0
for i in range(n):
	if a[i] in dic:
		count += 1
		if dic[a[i]] == 1:
			del dic[a[i]]
		else:
			dic[a[i]] -= 1
		if not dic:
			count -= 1
			ans.append(count + n - i)
			break
		else:
			ans.append(count)
		count = 0
	else:
		count += 1
print(totalprofit)
print(*ans)


from collections import defaultdict
(X, Numbers, MyDict, Now) = (list(map(int, input().split())), list(map(int, input().split())), defaultdict(int), 1)
(Temp, Answer) = (sorted(Numbers, reverse=True), [])
for i in range(X[1]):
	MyDict[Temp[i]] += 1
print(sum(Temp[:X[1]]))
i = 0
while X[1] != 1:
	if Numbers[i] in MyDict:
		MyDict[Numbers[i]] -= 1
		if MyDict[Numbers[i]] == 0:
			del MyDict[Numbers[i]]
		Answer.append(Now)
		(X[1], Now) = (X[1] - 1, 0)
	(i, Now) = (i + 1, Now + 1)
print(*Answer, X[0] - sum(Answer))


(n, k) = map(int, input().split())
q = n
a = [int(_) for _ in input().split()]
b = sorted(a)
c = b[n - k:n]
j = 0
print(sum(c))
for i in range(k - 1):
	d = 0
	while j < q:
		d += 1
		if a[j] in c:
			print(d, end=' ')
			n -= d
			del c[c.index(a[j])]
			j += 1
			break
		j += 1
print(n)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
c = [a.index(max(a))]
d = [a[c[-1]]]
for i in range(1, k):
	a[c[-1]] = -1
	c.append(a.index(max(a)))
	d.append(a[c[-1]])
c.sort()
print(sum(d))
if k > 1:
	print(c[1], end=' ')
	for i in range(1, len(c) - 1):
		print(c[i + 1] - c[i], end=' ')
	print(n - c[-1])
else:
	print(n)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
data = []
for i in range(len(arr)):
	data.append((arr[i], i + 1))
data.sort(reverse=1)
info = data[:k]
info.sort(key=lambda x: x[1])
answer = 0
for i in info:
	answer += i[0]
left = 0
cnt = 0
print(answer)
for i in range(len(info) - 1):
	print(info[i][1] - left, end=' ')
	cnt += info[i][1] - left
	left = info[i][1]
print(n - cnt)


import math, sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
lili = lambda : list(map(int, sys.stdin.readlines()))
li = lambda : list(map(int, input().split()))

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
(n, k) = li()
a = li()
v = a.copy()
v.sort(reverse=True)
b = v[0:k]
s = sum(b)
c = 0
print(s)
for i in range(0, n):
	if a[i] in b:
		c += 1
		if len(b) == 1:
			c = c + len(a) - i - 1
		print(c, end=' ')
		b.remove(a[i])
		c = 0
	else:
		c += 1
print()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l1 = sorted(l)
l1 = list(reversed(l1))
l1 = l1[:m]
c = 0
d = 0
e = 0
print(sum(l1))
for i in range(len(l)):
	if l[i] in l1 and c == 0 and (len(l1) > 1):
		c = 1
		d = i + 1
		e += d
		print(d, end=' ')
		l1.remove(l[i])
	elif len(l1) == 1:
		print(n - e)
		break
	elif c != 0 and l[i] in l1:
		l1.remove(l[i])
		d = i + 1 - e
		e += d
		print(d, end=' ')


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
b = []
b[:] = a
a.sort()
print(sum(a[-k:]))
arr = []
for i in range(len(b)):
	arr.append((b[i], i))
arr.sort()
p = [0 for i in range(n)]
for e in arr[-k:]:
	p[e[1]] = 1
j = 0
c = 0
for i in range(len(p)):
	if c == k - 1:
		break
	if p[i] == 1:
		print(i - j + 1, end=' ')
		j = i + 1
		c += 1
print(len(p) - j, end=' ')
print()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append((a[i], i))
b.sort(reverse=True)
sum = 0
lol = [-1]
for i in range(k):
	sum += b[i][0]
	lol.append(b[i][1])
lol.sort()
ans = []
for i in range(1, k + 1):
	ans.append(lol[i] - lol[i - 1])
ans[k - 1] += n - 1 - lol[k]
print(sum)
print(*ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
c = a[:]
a.sort(reverse=True)
b = [0] * (a[0] + 1)
ans = []
for i in range(k):
	b[a[i]] += 1
co = 0
for i in range(n):
	if len(ans) == k - 1:
		break
	if b[c[i]] > 0:
		b[c[i]] -= 1
		co += 1
		ans.append(co)
		co = 0
	else:
		co += 1
print(sum(a[:k]))
print(*ans, n - sum(ans))


(n, k) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
d = []
b = []
for i in range(len(a)):
	b.append(a[i])
b.sort()
b.reverse()
c = []
s = 0
for i in range(k):
	s += b[i]
	d.append(b[i])
print(int(s))
k = int(0)
for i in range(len(a)):
	k += 1
	if a[i] in d:
		c.append(k)
		d.remove(a[i])
		k = 0
		if len(d) == 0:
			l = i + 1
			break
if l < len(a):
	c[len(c) - 1] += len(a) - l
for i in range(len(c)):
	print(c[i], end=' ')


(n, k) = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
t = []
total_profit = 0
q = [(i, x) for (i, x) in enumerate(a)]
q.sort(key=lambda b: b[1], reverse=True)
q = q[:k]
q.sort(key=lambda b: b[0])
i = 0
while i < k:
	l = 0 if i == 0 else q[i][0]
	r = len(a) if i == k - 1 else q[i + 1][0]
	v = a[l:r]
	profit = max(v)
	total_profit += profit
	t.append(len(v))
	i += 1
print(total_profit)
print(*t)


(n, k) = map(int, input().split())
(s, t) = (list(map(int, input().split())), [])
c = s.copy()
for i in range(k):
	t.append(c.index(max(c)))
	c[t[i]] = 0
print(sum(s) - sum(c))
t.sort()
c = []
for (i, j) in zip(t[:-1], t[1:]):
	c.append(j - i)
c.append(n - t[-1])
c[0] += t[0]
print(' '.join((str(i) for i in c)))


(n, k) = tuple(map(int, input().split()))
A = list(map(int, input().split()))
copy = A[:]
copy.sort()
ans = copy[-k:]
count = 0
ans2 = []
print(sum(ans))
for index in range(len(A)):
	i = A[index]
	if len(ans) == 1:
		ans2.append(len(A[index:]))
		break
	if i not in ans:
		count += 1
	else:
		ans.pop(ans.index(i))
		ans2.append(count + 1)
		count = 0
for i in range(len(ans2) - 1):
	print(ans2[i], end=' ')
print(ans2[-1])


import sys
import math
(n, k) = map(int, input().split())
a = [*map(int, input().split())]
a = sorted(((a[i], i) for i in range(n)), reverse=True)[:k]
print(sum((v for (v, i) in a)))
a = sorted((i for (v, i) in a))
a[-1] = n - 1
print(' '.join((str(y - x) for (x, y) in zip([-1] + a, a))))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a2 = sorted(a, reverse=True)
x = [0 for i in range(n)]
for i in range(k):
	for j in range(n):
		if a[j] == a2[i] and x[j] == 0:
			x[j] = 1
			break
ans = []
cnt_biggest = 0
cnt_element = 0
for i in range(n):
	if x[i] > 0:
		if cnt_biggest == 0:
			cnt_biggest += 1
			cnt_element += 1
		else:
			ans.append(cnt_element)
			cnt_element = 1
	else:
		cnt_element += 1
ans.append(cnt_element)
print(sum(a2[:k]))
print(*ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(a)
b.sort()
c = []
sum = 0
for i in range(1, k + 1):
	c.append(b[-i])
	sum += b[-i]
print(sum)
d = []
for i in range(n):
	if a[i] in c:
		d.append(i)
		c.remove(a[i])
	else:
		pass
d.insert(0, -1)
d[-1] = n - 1
e = []
for i in range(1, len(d)):
	e.append(d[i] - d[i - 1])
print(' '.join(map(str, e)))


(n, k) = [int(x) for x in input().split()]
lst = [int(x) for x in input().split()]
lst_check = [1] * k + [0] * (n - k)
idx_lst = list(range(k))
for i in range(k):
	for j in range(n):
		if lst_check[j]:
			continue
		elif lst[j] > lst[idx_lst[i]]:
			lst_check[idx_lst[i]] = 0
			idx_lst[i] = j
			lst_check[idx_lst[i]] = 1
idx_lst.sort()
print(sum([lst[i] for i in idx_lst]))
if k == 1:
	print(n)
else:
	seq = [idx_lst[0] + 1] + [idx_lst[x] - idx_lst[x - 1] for x in range(1, k - 1)]
	if n >= 2:
		seq.append(n - idx_lst[k - 2] - 1)
	print(' '.join(map(str, seq)))


(n, k) = (int(i) for i in input().split())
l = [int(i) for i in input().split()]
l1 = sorted(l, reverse=True)
l1 = l1[:k]
s = sum(l1)
print(s)
l2 = []
k1 = 0
prev = 0
for i in range(n):
	if k1 == k - 1:
		l2.append(n - i)
		break
	if l[i] in l1:
		l1[l1.index(l[i])] = -1
		if k1 == 0:
			l2.append(i - prev + 1)
		else:
			l2.append(i - prev)
		k1 += 1
		prev = i
print(*l2)


l = [int(x) for x in input().split()]
n = l[0]
k = l[1]
t = [int(x) for x in input().split()]
mark = [0] * n
b = t.copy()
b.sort()
prof = 0
pos = []
for i in range(k):
	prof += b[n - 1 - i]
d = 0
smax = 2001
for i in range(n):
	maxi = -1
	ptr = -1
	for j in range(n):
		if t[j] > maxi and mark[j] == 0:
			maxi = t[j]
			ptr = j
	smax = maxi
	mark[ptr] = 1
	pos.append(ptr)
	d += 1
	if d == k:
		break
print(prof)
f = pos.copy()
f.sort()
num = []
start = 0
fin = -1
j = 0
while start <= n - 1:
	if j == k - 1:
		num.append(n - 1 - start + 1)
		start = n
	else:
		num.append(f[j] - start + 1)
		start = f[j] + 1
	j += 1
for i in range(k):
	print(num[i], end=' ')


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
m = 0
for i in range(k):
	h = max(a)
	a[a.index(h)] = -1
	m += h
print(m)
j = 0
p = 0
for i in range(k - 1):
	while a[j] != -1:
		j += 1
	print(j + 1 - p, end=' ')
	p = j + 1
	j += 1
print(n - j)


(n, k) = tuple(map(int, input().split()))
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append((a[i], i))
b = sorted(b, reverse=True)
c = []
ans = 0
for i in range(k):
	ans += b[i][0]
	c.append(b[i][1])
c = sorted(c)
print(ans)
if k == 1:
	print(n)
	exit()
for i in range(len(c)):
	if i == len(c) - 1:
		print(n - c[i - 1] - 1, end=' ')
	elif i == 0:
		print(c[i] + 1, end=' ')
	else:
		print(c[i] - c[i - 1], end=' ')


import collections
from functools import cmp_to_key
import math
import sys

def getIntList():
	return list(map(int, input().split()))
import bisect
try:
	import numpy
	dprint = print
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass

def makePair(z):
	return [(z[i], z[i + 1]) for i in range(0, len(z), 2)]

def memo(func):
	cache = {}

	def wrap(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return wrap

@memo
def comb(n, k):
	if k == 0:
		return 1
	if n == k:
		return 1
	return comb(n - 1, k - 1) + comb(n - 1, k)
(N, K) = getIntList()
za = getIntList()
flag = [0 for i in range(N)]
zz = [(za[i], i) for i in range(N)]
zz.sort(reverse=True)
tot = 0
for i in range(K):
	t = zz[i][1]
	flag[t] = 1
	tot += za[t]
print(tot)
last = -1
res = []
for i in range(N):
	if flag[i]:
		res.append(i - last)
		last = i
res[-1] += N - last - 1
for x in res:
	print(x, end=' ')


(n, k) = [int(i) for i in input().split()]
l = []
m = []
l = [int(i) for i in input().split()]
m = [i for i in l]
m.sort()
m = m[n - k:n]
start = 0
visited = []
sizes = []
works = 0
print(sum(m))
for i in range(1, n + 1):
	s = max(l[start:i])
	if s in m:
		m[m.index(s)] = -1
		sizes.append(len(l[start:i]))
		start = i
sizes[-1] += n - start
b = ''
for i in sizes:
	b += str(i) + ' '
print(b)


(n, k) = map(int, input().split())
values = list(map(int, input().split()))
maximums = sorted(values)[n - k:n]
s = sum(maximums)
count = 1
answer = []
for value in values:
	if value in maximums and len(maximums) > 1:
		answer.append(count)
		maximums.remove(value)
		count = 1
	else:
		count += 1
answer.append(count - 1)
print(s)
print(' '.join([str(x) for x in answer]))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def main():
	(n, k) = LI()
	a = LI()
	t = sorted(sorted(range(n), key=lambda x: -a[x])[:k])
	r = sum((a[i] for i in t))
	t[-1] = n - 1
	rr = []
	c = -1
	for i in t:
		rr.append(i - c)
		c = i
	return '{}\n{}'.format(r, ' '.join(map(str, rr)))
print(main())


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
if k == 1:
	print(max(arr))
	print(n)
	exit()
arr1 = sorted(arr)
arr1 = arr1[n - k:]
print(sum(arr1))
ini = -1
lens = []
for i in range(n):
	if arr[i] in arr1:
		arr1.remove(arr[i])
		if len(arr1) == 0:
			lens.append(i - ini + (n - 1 - i))
			break
		else:
			lens.append(i - ini)
			ini = i
print(*lens)


(n, k) = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
maxsum = 0
vmax = dict()
for x in sorted(q)[-k:]:
	maxsum += x
	if x in vmax:
		vmax[x] += 1
	else:
		vmax[x] = 1
sep = 1
ans = []
for i in range(n):
	x = q[i]
	if x in vmax and vmax[x]:
		vmax[x] -= 1
		if len(ans) + 1 == k:
			sep += n - i - 1
		ans.append(sep)
		sep = 1
	else:
		sep += 1
print(maxsum)
print(' '.join(map(str, ans)))


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [[a[i], i] for i in range(n)]
b.sort(reverse=True)
b = b[:k]
b.sort(key=lambda x: x[1])
ans = 0
for i in b:
	ans += i[0]
print(ans)
prev = 0
for (iter, i) in enumerate(b):
	if iter != len(b) - 1:
		print(i[1] + 1 - prev, end=' ')
		prev = i[1] + 1
	else:
		print(n - prev)


(a, d) = map(int, input().split())
b = list(map(int, input().split()))
c = b[:]
sum = 0
count = 0
m = d
p = [0 for i in range(a)]
c.sort(reverse=True)
for i in range(d):
	sum = sum + c[i]
	for j in range(a):
		if b[j] == c[i] and p[j] == 0:
			p[j] = 1
			break
print(sum)
for i in range(a):
	count = count + 1
	if m == 1:
		print(a - i)
		break
	elif p[i] == 1:
		print(count, end=' ')
		count = 0
		m -= 1


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
z = sorted(l, reverse=True)
d = {}
sumi = 0
for i in range(k):
	sumi = sumi + z[i]
	if z[i] not in d:
		d[z[i]] = 1
	else:
		d[z[i]] = d[z[i]] + 1
out = ''
temp = 0
e = 0
for i in range(n):
	if l[i] in d:
		if d[l[i]] > 0:
			temp = temp + 1
			e = e + 1
			if e == k:
				out = out + ' ' + str(temp + n - i - 1)
				break
			d[l[i]] = d[l[i]] - 1
			out = out + ' ' + str(temp)
			temp = 0
		else:
			temp = temp + 1
	else:
		temp = temp + 1
print(sumi)
print(out)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a1 = sorted(a, reverse=True)[:k]
ind = []
for i in range(len(a1)):
	ind.append(a.index(a1[i]))
	a[a.index(a1[i])] = 0
ind.sort()
result = []
for i in range(1, len(ind)):
	result.append(ind[i] - ind[i - 1])
result.append(len(a) - ind[-1])
if len(ind) > 1:
	result[0] = ind[1]
else:
	result[0] = len(a)
print(sum(a1))
for i in result:
	print(i, end=' ')


(problems, days) = list(map(int, input().split(' ')))
difficulties = list(map(int, input().split(' ')))
copyDifficulties = difficulties.copy()
copyDifficulties.sort()
maxValues = {}
for i in range(days):
	if copyDifficulties[problems - 1 - i] in maxValues:
		maxValues[copyDifficulties[problems - i - 1]] += 1
	else:
		maxValues[copyDifficulties[problems - i - 1]] = 1
gained = 0
solved = []
solvedDay = 0
for i in range(problems):
	solvedDay += 1
	if difficulties[i] in maxValues and maxValues.get(difficulties[i]) >= 1:
		gained += difficulties[i]
		maxValues[difficulties[i]] -= 1
		solved.append(solvedDay)
		solvedDay = 0
solved[len(solved) - 1] += problems - sum(solved)
print(gained)
res = ' '
for i in solved:
	res += str(i) + ' '
print(res.strip())


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if k == 1:
	print(max(a))
	print(n)
else:
	b = sorted(a)
	c = []
	d = []
	x = 0
	for i in range(-1, -k - 1, -1):
		c.append(b[i])
	print(sum(c))
	while x < k:
		for i in range(n):
			if a[i] == c[x]:
				d.append(i)
				x += 1
				if x == k:
					break
	d.sort()
	print(d[1], end=' ')
	for i in range(2, k):
		print(d[i] - d[i - 1], end=' ')
	print(n - d[-1])


(n, m) = map(int, input().split())
ls = [int(i) for i in input().split()]
s = sorted(ls)
s.reverse()
st = s[:m]
print(sum(s[:m]))
l = -1
for (i, j) in enumerate(ls):
	if j in st:
		if len(st) == 1:
			exit(print(n - l - 1))
		st.pop(st.index(j))
		print(i - l, end=' ')
		l = i


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
d = dict()
b = list(map(int, input().split()))
for j in range(n):
	d[b[j]] = []
for j in range(n):
	d[b[j]].append(j + 1)
a = b.copy()
a.sort(reverse=True)
c = a[:k]
e = []
for j in range(k):
	e.append(d[c[j]][-1])
	d[c[j]].pop()
e.sort()
f = []
p = 0
for j in range(k):
	f.append(e[j] - p)
	p = e[j]
f[-1] = n - sum(f[:k - 1])
print(sum(c))
print(*f)


(n, k) = map(int, input().split())
L = list(map(int, input().split()))
s = sorted(L, reverse=True)
p = []
for i in range(k):
	a = L.index(s[i])
	p.append(a + 1)
	L[a] = -1
p = sorted(p)
res = []
if p[k - 1] != n:
	p[k - 1] = n
p = [0] + p
for i in range(1, k + 1):
	res.append(p[i] - p[i - 1])
print(sum(s[:k]))
print(*res)


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
dp = a.copy()
dp.sort(reverse=True)
d = defaultdict(int)
tp = 0
for i in range(k):
	tp += dp[i]
	if dp[i] not in d:
		d[dp[i]] = 1
	else:
		d[dp[i]] += 1
ans = []
i1 = -1
for i in range(n):
	if d[a[i]] > 0:
		d[a[i]] -= 1
		ans.append(i - i1)
		i1 = i
ans[-1] += i - i1
print(tp)
print(*ans)


(x, y) = map(int, input().split())
z = list(map(int, input().split()))
c = []
for i in z:
	c.append(i)
c.sort()
c = c[-y:]
b = sum(c)
k = [0]
s = ''
for i in range(x):
	if z[i] in c:
		k.append(i)
		c.remove(z[i])
k.append(x)
s += str(k[1] - k[0] + k[2] - k[1]) + ' '
for i in range(2, y + 1):
	s += str(k[i + 1] - k[i]) + ' '
print(b)
print(s)


(n, k) = [int(x) for x in input().split()]
L = [int(x) for x in input().split()]
S = sorted(L, reverse=True)
print(sum(S[:k]))
D = {}
for i in range(n):
	if L[i] in D:
		D[L[i]].append(i)
	else:
		D[L[i]] = [i]
Positions = []
for i in S[:k]:
	Positions.append(D[i][-1])
	D[i].pop()
Positions.sort()
Solved = []
for i in range(k - 1):
	Solved.append(Positions[i + 1] - Positions[i])
Solved.append(n - Positions[-1])
Solved[0] += Positions[0]
for i in Solved:
	print(i, end=' ')


R = lambda : map(int, input().split())
(n, k) = R()
a = sorted(zip(R(), range(n)))[-k:]
print(sum((x[0] for x in a)))
b = sorted((x[1] for x in a))
if k > 1:
	print(b[1], *(y - x for (x, y) in zip(b[1:], b[2:] + [n])))
else:
	print(n)


import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
digl = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
(n, k) = f()
l = sorted(enumerate(il()), key=lambda x: x[1], reverse=True)
l2 = sorted(l[:k])
sm = sum((y for (x, y) in l2))
print(sm)
l2 = [x for (x, y) in l2]
l2[0] = 0
l2 += [n]
print(*(y - x for (x, y) in zip(l2, l2[1:])))


input1 = list(map(int, input().split()))
input2 = list(map(int, input().split()))
cinput2 = input2.copy()
n = input1[0]
k = input1[1]
listofmax = []
listofind = []
if k == 1:
	print(max(input2))
	print(len(input2))
else:
	for i in range(k):
		maxi = max(cinput2)
		listofmax.append(maxi)
		listofind.append(cinput2.index(maxi))
		maxind = cinput2.index(maxi)
		cinput2[maxind] = -10.5
	s = sum(listofmax)
	print(s)
	result = []
	indm1 = min(listofind)
	result.append(indm1 + 1)
	listofind.remove(indm1)
	for i in range(len(listofind) - 1):
		indm2 = indm1
		indm1 = min(listofind)
		result.append(indm1 - indm2)
		listofind.remove(indm1)
	result.append(len(input2) - indm1 - 1)
	print(*result)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
biggest = sorted(enumerate(a), key=lambda x: x[1])[-k:]
byIndex = sorted(biggest)
mx = 0
groups = []
start = 0
for (a, b) in byIndex:
	mx += b
	groups.append(a + 1 - start)
	start = a + 1
groups[-1] -= sum(groups) - n
print(mx)
print(' '.join(map(str, groups)))


n_k = list(map(int, input().split()))
problems = list(map(int, input().split()))
problems_tup_list = list()
n = n_k[0]
k = n_k[1]
for (idx, prob) in enumerate(problems):
	problems_tup_list.append((idx, prob))
sorted_problems_tup = sorted(problems_tup_list, key=lambda val: val[1], reverse=True)
max_profit = 0
ans_num = list()
for p in range(k):
	idx = sorted_problems_tup[p][0]
	val = sorted_problems_tup[p][1]
	max_profit += val
	ans_num.append(idx)
ans_num = sorted(ans_num)
ans_string = ''
cur_sum = 0
if k != 1:
	for (idx_, ans) in enumerate(ans_num):
		if idx_ == 0:
			cur_sum += ans + 1
			ans_string += str(ans + 1)
			ans_string += ' '
		elif idx_ < k - 1:
			cur_sum += ans - ans_num[idx_ - 1]
			ans_string += str(ans - ans_num[idx_ - 1])
			ans_string += ' '
		else:
			ans_string += str(n - cur_sum)
else:
	ans_string += str(n)
print(max_profit)
print(ans_string)


(n, k) = map(int, input().split())
a = map(int, input().split())
at = []
z = 0
for i in a:
	at.append((z, i))
	z = z + 1
at.sort(key=lambda x: -x[1])
zt = sorted(at[:k], key=lambda x: x[0])
prev = -1
ai = []
suma = 0
for i in zt:
	ai.append(i[0] - prev)
	prev = i[0]
	suma += i[1]
ai[-1] = ai[-1] + (n - sum(ai))
print(suma)
print(' '.join((str(i) for i in ai)))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted([(x, i) for (i, x) in enumerate(l)], key=lambda x: (x[0], x[1]))
used = l[-k:]
s = sum((x[0] for x in used))
days = sorted((x[1] for x in used))
print(s)
d = []
t = 0
for x in days[:-1]:
	d.append(x - t + 1)
	t = x + 1
d.append(n - t)
print(*d)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ret = 0
	ret0 = []
	b = sorted(a, reverse=True)
	dct = {}
	for i in range(k):
		try:
			dct[b[i]] += 1
		except:
			dct[b[i]] = 1
	ind = 0
	temp = 0
	rets = 0
	while rets < k - 1:
		temp += 1
		try:
			if dct[a[ind]]:
				dct[a[ind]] -= 1
				ret += a[ind]
				ret0.append(str(temp))
				temp = 0
				rets += 1
		except:
			pass
		ind += 1
	ret0.append(str(n - ind))
	ret += max(a[ind:])
	print(ret)
	print(' '.join(ret0))
	return 0
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)[:k]
print(sum(b))
c = []
l = 0
r = -1
while len(b) > 0:
	if a[l] in b:
		c.append(l - r)
		r = l
		b.remove(a[l])
	l += 1
c[-1] += len(a) - l
print(*c)


(m, n) = map(int, input().split())
l = list(map(int, input().split()))
z = []
for i in range(m):
	z.append(i + 1)
a = list(zip(l, z))
a.sort(reverse=True)
sum = 0
for i in range(n):
	sum += a[i][0]
p = []
print(sum)
for i in range(n):
	p.append(a[i][1])
p.sort()
k = []
flag = 0
sum = 0
for i in range(n - 1):
	x = p[i] - flag
	flag = p[i]
	sum += x
	k.append(x)
k.append(m - sum)
tt = len(k)
for i in k:
	print(i, end=' ')
print()


from __future__ import print_function
import sys
import math
import os.path
import random
from copy import deepcopy
from functools import reduce
from collections import Counter, ChainMap, defaultdict
from itertools import cycle, chain
from queue import Queue, PriorityQueue
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, nlargest, nsmallest
import bisect
from statistics import mean, mode, median, median_low, median_high
sys.setrecursionlimit(10 ** 9)

def log(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)

def ni():
	return map(int, input().split())

def nio(offset):
	return map(lambda x: int(x) + offset, input().split())

def nia():
	return list(map(int, input().split()))

def toString(aList, sep=' '):
	return sep.join((str(x) for x in aList))

def toMapInvertIndex(aList):
	return {k: v for (v, k) in enumerate(aList)}

def sortId(arr):
	return sorted(range(len(arr)), key=lambda k: arr[k])
(n, k) = ni()
a = nia()
ai = sortId(a)[-k:]
ai.sort()
print(sum((a[i] for i in ai)))
ai[-1] = len(a) - 1
ai = [x + 1 for x in ai]
for i in range(len(ai) - 1, 0, -1):
	ai[i] -= ai[i - 1]
print(toString(ai))


(n, m) = map(int, input().split())
lst = list(map(int, input().split()))
arr = lst.copy()
arr.sort(reverse=True)
vis = [0] * n
summ = 0
for i in range(m):
	temp = arr[i]
	summ += temp
	for j in range(n):
		if vis[j] == 0 and lst[j] == temp:
			vis[j] = 1
			break
print(summ)
cnt = 0
ans = []
for i in range(n):
	if vis[i] == 1:
		ans.append(cnt + 1)
		cnt = 0
	else:
		cnt += 1
ans[-1] += cnt
print(*ans)


(n, k) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
res = sorted(a, reverse=True)
res = res[0:k]
print(sum(res))
s = res
prev = 0
counter = 1
for i in range(len(a)):
	if a[i] in s:
		s.pop(s.index(a[i]))
		if counter == k:
			print(n - prev)
		else:
			print(i + 1 - prev, end=' ')
		counter += 1
		prev = i + 1


(n, m) = map(int, input().split())
ls = [int(i) for i in input().split()]
t = sorted(ls)
t.reverse()
ans = 0
st = []
for i in range(m):
	ans += t[i]
	st.append(t[i])
print(ans)
l = -1
for i in range(n):
	if ls[i] in st:
		if len(st) == 1:
			print(n - 1 - l)
			return
		st.pop(st.index(ls[i]))
		print(i - l, end=' ')
		l = i


from sys import stdin, stdout
import cProfile, math, copy
printHeap = str()
test = False

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def test_print(output):
	if test:
		stdout.write(str(output) + '\n')

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def get_int():
	return int(stdin.readline())

def get_tuple():
	return map(int, stdin.readline().split())

def get_str_list():
	return list(map(str, stdin.readline().split()))

def get_list():
	return list(map(int, stdin.readline().split()))
arguments = list()
results = list()

def clear_cache():
	global arguments, results
	(arguments, results) = (list(), list())

def cached_fn(fn, *args):
	global arguments, results
	if args in arguments:
		return results[arguments.index(args)]
	else:
		result = fn(*args)
		arguments.append(args)
		results.append(result)
		return result

def main():
	(n, k) = get_tuple()
	arr = get_list()
	sorted = copy.deepcopy(arr)
	sorted.sort(reverse=True)
	sorted = sorted[0:k]
	t = list()
	(max, last) = (0, -1)
	for (i, ele) in enumerate(arr):
		if ele in sorted:
			max += ele
			sorted.remove(ele)
			if len(sorted) == 0:
				t.append(n - 1 - last)
				break
			t.append(i - last)
			last = i
	display(max)
	display_list(t)
cProfile.run('main()') if test else main()


from math import *
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = a.copy()
b.sort()
b = b[-k:]
c = []
col = 0
sum = 0
for elem in b:
	sum += elem
for i in range(n):
	col += 1
	if b.count(a[i]) != 0:
		b.pop(b.index(a[i]))
		if len(b) == 0:
			c.append(col + (n - 1 - i))
			break
		else:
			c.append(col)
		col = 0
print(sum)
print(*c)


def main():
	(n, k) = (int(i) for i in input().split())
	a = [int(i) for i in input().split()]
	aa = [i for i in range(n)]
	aa.sort(key=lambda x: a[x], reverse=True)
	aa = aa[0:k]
	aa.sort()
	s = 0
	for e in aa:
		s += a[e]
	print(s)
	if k > 1:
		r = [aa[1]]
		for e in range(2, k):
			r.append(aa[e] - aa[e - 1])
		r.append(n - aa[len(aa) - 1])
		print(' '.join(map(str, r)))
	else:
		print(n)
main()


def main():
	import sys
	from collections import defaultdict
	(n, k) = [int(x) for x in sys.stdin.readline().strip('\n').split(' ')]
	problems = [int(x) for x in sys.stdin.readline().strip('\n').split(' ')]
	sor = sorted(problems, key=lambda x: x, reverse=True)
	k_sor = sor[0:k]
	seen = defaultdict(int)
	for x in k_sor:
		seen[x] += 1
	ans = 0
	for i in range(0, k):
		ans += sor[i]
	print(ans)
	curr_solved = 0
	ans_arr = []
	for i in range(0, len(problems)):
		curr_solved += 1
		if problems[i] in k_sor and seen[problems[i]] > 0:
			seen[problems[i]] -= 1
			ans_arr.append(curr_solved)
			curr_solved = 0
	ans_arr[-1] += len(problems) - sum(ans_arr)
	print(*ans_arr)
main()


(n, k) = map(int, input().split())
a = [int(_) for _ in input().split()]
q = sorted(a)[::-1][:k]
p = 1
u = 0
print(sum(q[:k]))
for j in range(n):
	for i in range(k):
		if a[j] == q[i]:
			q[i] = -1
			a[j] = -1
for w in range(n):
	if p == k and a[w] == -1:
		print(n - u)
		break
	elif a[w] == -1:
		a[w] = -2
		print(w + 1 - u, end=' ')
		p += 1
		u += w + 1 - u


(n, k) = map(int, input().split())
a = sorted(enumerate(map(int, input().split())), key=lambda x: -x[1])[:k]
s = 0
for i in a:
	s += i[1]
a.sort(key=lambda x: x[0])
print(s)
prev = -1
for i in a[:-1]:
	print(i[0] - prev, end=' ')
	prev = i[0]
print(n - prev - 1)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
Read = lambda : list(map(int, input().split()))
Num = lambda : int(input())

def solve():
	(n, k) = Read()
	a = Read()
	b = list(enumerate(a))
	b.sort(key=lambda i: i[1])
	tot = 0
	need = []
	for i in b[-k:]:
		tot += i[1]
		need.append(i[0])
	need.sort()
	ans = [a[i:j] for (i, j) in zip([0] + need, need + [None])]
	ans[0] = ans[0] + ans[1]
	ans.pop(1)
	print(tot)
	for i in ans:
		print(len(i), end=' ')
	print()
solve()


import copy
(n, k) = [int(x) for x in input().split()]
problems = [int(x) for x in input().split()]
problemsnew = copy.deepcopy(sorted(problems, reverse=True)[:k])
benefit = sum(problemsnew)
num = 0
output = []
for i in range(n):
	num += 1
	if problems[i] in problemsnew:
		output.append(num)
		problemsnew.remove(problems[i])
		num = 0
output[-1] = output[-1] + n - sum(output)
print(benefit)
print(' '.join([str(x) for x in output]))


(n, k) = list(map(int, input().split()))
a_copy = list(map(int, input().split()))
a = a_copy[:]
c = [0] * k
c_places = [0] * k
for i in range(k):
	c[i] = max(a)
	c_places[i] = a.index(max(a))
	a[a.index(max(a))] = 0
c_places.sort()
if n == 1:
	print(sum(c))
	print(n)
else:
	print(sum(c))
	tmp = 0
	for i in range(len(c_places) - 1):
		print(len(a[tmp:c_places[i] + 1]), end=' ')
		tmp += len(a[tmp:c_places[i] + 1])
	print(len(a[tmp:]))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
arr = list(a)
a.sort(reverse=True)
s = 0
d = {}
for i in range(k):
	s += a[i]
	if a[i] in d:
		d[a[i]] += 1
	else:
		d[a[i]] = 1
ans = []
c = 0
for i in range(n):
	c += 1
	if arr[i] in d and d[arr[i]] > 0:
		d[arr[i]] -= 1
		ans.append(c)
		c = 0
temp = 0
for i in range(k - 1):
	temp += ans[i]
ans[-1] = n - temp
print(s)
print(*ans)


import math
(n, t) = list(map(int, input().split()))
m = list(map(int, input().split()))
ans = m
maxi = []
mm = []
for i in range(t):
	mm.append(max(ans))
	maxi.append(ans.index(mm[-1]))
	ans[maxi[i]] = -1
maxi.sort()
maxi[0] = 0
ans2 = []
for i in range(t - 1):
	ans2.append(maxi[i + 1] - maxi[i])
ans2.append(n - maxi[-1])
print(sum(mm))
for i in ans2:
	print(i, end=' ')


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
b = []
for i in range(n):
	b.append((a[i], i))
b.sort()
b = b[n - k:n]
sum_ = 0
for i in range(len(b)):
	sum_ += b[i][0]
print(sum_)
b.sort(key=lambda x: x[1])
b.append((0, n))
for i in range(k):
	if i == 0:
		print(b[i + 1][1], end=' ')
	else:
		print(b[i + 1][1] - b[i][1], end=' ')


(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
b = a[:]
b.sort(reverse=True)
b = b[:k]
su = 0
for x in b:
	su += x
print(su)
i = 0
pred = -1
while i < n and len(b) > 1:
	j = -1
	for q in range(len(b)):
		if b[q] == a[i]:
			j = q
	if j != -1:
		print(i - pred, end=' ')
		pred = i
		i += 1
		b = b[:j] + b[j + 1:len(b)]
	else:
		i += 1
print(n - pred - 1)


(n, k) = input().split()
n = int(n)
k = int(k)
a = [int(x) for x in input().split()]
biggest = sorted(a, reverse=True)[:k]
print(sum(biggest))
first_max = False
if a[0] in biggest:
	first_max = True
	biggest.remove(a[0])
	k -= 1
last = 0
for (i, num) in enumerate(a):
	if first_max:
		if i == 0:
			continue
		if num in biggest:
			print(i - last, end=' ')
			biggest.remove(num)
			last += i - last
			k -= 1
			first_max = False
	elif num in biggest:
		if last == 0:
			biggest.remove(num)
			k -= 1
			first_max = True
		else:
			print(i - last, end=' ')
			biggest.remove(num)
			last += i - last
			k -= 1
print(n - last, end=' ')


def go():
	from collections import Counter
	(n, k) = (int(i) for i in input().split(' '))
	a = [int(i) for i in input().split(' ')]
	s = sorted(a, reverse=True)[:k]
	s_a = Counter(s)
	j = -1
	output = []
	for i in range(n):
		if a[i] in s_a:
			output.append(str(i - j))
			j = i
			if s_a[a[i]] == 1:
				s_a.pop(a[i])
			else:
				s_a[a[i]] -= 1
	output[-1] = str(int(output[-1]) + i - j)
	print(sum(s))
	return ' '.join(output)
print(go())


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = []
pos = []
for (i, v) in enumerate(arr):
	dic = dict()
	dic['index'] = i + 1
	dic['val'] = v
	arr1.append(dic)
arr1.sort(key=lambda x: x['val'], reverse=True)
maxx = 0
for i in range(k):
	maxx += arr1[i]['val']
	pos.append(arr1[i]['index'])
print(maxx)
pos.append(n + 1)
pos.sort()
temp_arr = [str(pos[1] - 1)]
for i in range(1, k):
	temp_arr.append(str(pos[i + 1] - pos[i]))
print(' '.join(temp_arr))


from operator import itemgetter
(n, k) = map(int, input().split())
D = [(i + 1, v) for (i, v) in enumerate(map(int, input().split()))]
X = sorted(D, key=itemgetter(1), reverse=True)[:k]
Y = sorted(X)
print(sum(map(itemgetter(1), Y)))
days = [Y[0][0] if k > 1 else n] + [y[0] - Y[i][0] for (i, y) in enumerate(Y[1:-1])] + ([] if k < 2 else [n - Y[-2][0]])
print(' '.join(map(str, days)))


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = sorted(arr)
k1 = arr1[n - k:]
ans = []
sett = set()
last = -1
d = {}
for i in k1:
	d[i] = d.get(i, 0) + 1
for i in range(n):
	if d.get(arr[i], 0) > 0:
		ans.append(i)
		d[arr[i]] = d.get(arr[i], 0) - 1
ans1 = []
ans1.append(ans[0] + 1)
for i in range(1, len(ans)):
	ans1.append(ans[i] - ans[i - 1])
ans1[-1] += n - 1 - ans[-1]
print(sum(k1))
print(*ans1)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
indeces = sorted([[a[i], i] for i in range(n)], key=lambda x: x[0], reverse=True)[:k]
print(sum([indeces[i][0] for i in range(k)]))
indeces = sorted(indeces, key=lambda x: x[1])
if k >= 2:
	ans = [indeces[0][1] + 1]
	for i in range(1, k - 1):
		ans.append(indeces[i][1] - indeces[i - 1][1])
	ans.append(n - indeces[k - 2][1] - 1)
else:
	ans = [n]
print(' '.join(list(map(str, ans))))


import heapq
(n, k) = map(int, input().split())
a = list(enumerate(map(int, input().split()), 1))
s = heapq.nlargest(k, a, key=lambda x: x[1])
su = sum([si[1] for si in s])
s = sorted([si[0] for si in s])
s[-1] = n
for i in range(len(s) - 1, 0, -1):
	s[i] -= s[i - 1]
print(su)
print(*s)


import sys
inp = sys.stdin.readlines()
ii = 0
out = []
(n, k) = map(int, inp[ii].split())
ii += 1
probs = [int(z) for z in inp[ii].split()]
probs = []
for z in range(n):
	probs.append([int(inp[ii].split()[z]), z])
ii += 1
probsorted = sorted(probs, reverse=True)[:k]
total_profit = [sum((probsorted[r][0] for r in range(k)))]
indexes = sorted([probsorted[r][1] for r in range(k)])
maxnums = probsorted[:k]
maxindexes = []
used = []
res = []
if k == 1:
	out.append(str(probsorted[0][0]))
	out.append('\n')
	out.append(str(n))
else:
	for i in range(k - 1):
		if i == 0:
			res.append(str(indexes[i] + 1))
		else:
			res.append(str(indexes[i] - indexes[i - 1]))
	if len(indexes) >= 2:
		res.append(str(n - 1 - indexes[-2]))
	out.append(str(total_profit[0]))
	out.append('\n')
	out.append(' '.join(res))
sys.stdout.write(''.join(out))


(n, k) = map(int, input().split())
nth_p = list(map(int, input().split()))
sor = sorted(nth_p)
ods = []
count = od_max = tp_co = 0
for i in range(n - 1, n - k - 1, -1):
	count += sor[i]
	i_n = nth_p.index(sor[i])
	ods.append(i_n)
	nth_p[i_n] = -1
print(count)
ods.sort()
ods = [-1] + ods
for i in range(1, len(ods) - 1):
	print(ods[i] - ods[i - 1], end=' ')
print(n - ods[-2] - 1)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = a[:]
b.sort()
total = 0
c = []
for i in range(n - 1, n - k - 1, -1):
	total += b[i]
	c.append(b[i])
day = 0
b = []
for i in range(n):
	if a[i] in c:
		ind = c.index(a[i])
		c[ind] = -1
		k -= 1
		inda = i + 1
		if k == 0:
			temp = n - day
		else:
			temp = inda - day
			day = inda
		b.append(temp)
print(total)
for i in range(len(b)):
	print(b[i], end=' ')


def test_1():
	import math
	from collections import Counter
	(n, k) = list(map(int, input().split(' ')))
	data = list(map(int, input().split(' ')))
	a = sorted(data, reverse=1)
	idx = sorted(range(n), key=lambda k: data[k], reverse=1)
	print(sum(a[:k]))
	dd = []
	idx_2 = sorted(idx[:k])
	idx_2 = [i + 1 for i in idx_2]
	if k == 1:
		print(n)
	else:
		for i in range(k):
			if i == 0:
				d = idx_2[i]
			elif i == k - 1:
				d = n - idx_2[i - 1]
			else:
				d = idx_2[i] - idx_2[i - 1]
			dd.append(str(d))
		print(' '.join(dd))
test_1()


import heapq
(n, k) = map(int, input().split())
a = tuple(map(int, input().split()))
largest = heapq.nlargest(k, range(n), a.__getitem__)
rest = [False] * n
res = 0
for i in largest:
	rest[i] = True
	res += a[i]
print(res)
res = []
cur_group = 1
prev_group = 4000
for res_ti in rest:
	if res_ti:
		if prev_group != 4000:
			res.append(prev_group)
		prev_group = cur_group
		cur_group = 1
	else:
		cur_group += 1
res.append(cur_group + prev_group - 1)
print(*res)


(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
b = sorted(a, reverse=True)
b = b[:k]
print(sum((b[i] for i in range(k))))
l = 0
for r in range(n):
	if a[r] in b:
		print(r - l + 1 if k > 1 else n - l, end=' ')
		b.remove(a[r])
		l = r + 1
		k -= 1


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
p = [[] for i in range(2001)]
for i in range(n):
	p[a[i]] += [i + 1]
t = []
ans = 0
for i in range(2000, 0, -1):
	if k == 0:
		break
	c = min(len(p[i]), k)
	t += p[i][:c]
	k -= c
	ans += c * i
print(ans)
t.sort()
t[-1] = n
c = 0
for i in range(len(t)):
	(t[i], c) = (t[i] - c, t[i])
print(*t)


(n, k) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
a_sorted = sorted(zip(a, range(n)), key=lambda x: x[0])
maxK = a_sorted[-k:]
maxK = sorted(maxK, key=lambda x: x[1])
maxIndices = [x[1] + 1 for x in maxK]
t = maxIndices.copy()
for i in range(1, len(maxIndices)):
	t[i] -= maxIndices[i - 1]
t[-1] = n - sum(t[:-1])
print(sum((x[0] for x in maxK)))
print(' '.join([str(x) for x in t]))


from collections import deque
import heapq
import sys
input = sys.stdin.readline

def bfs():
	ans = [1] * k
	q = deque()
	color = [-1] * n
	for i in s:
		q.append(i)
		color[i] = i
	while q:
		i = q.popleft()
		if i - 1 >= 0:
			if color[i - 1] == -1:
				color[i - 1] = color[i]
				ans[r[color[i]]] += 1
				q.append(i - 1)
		if i + 1 < n:
			if color[i + 1] == -1:
				color[i + 1] = color[i]
				ans[r[color[i]]] += 1
				q.append(i + 1)
	return ans
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
h = []
for i in range(n):
	heapq.heappush(h, (-a[i], i))
s = []
ans = 0
for _ in range(k):
	(ai, i) = heapq.heappop(h)
	ans -= ai
	s.append(i)
print(ans)
s.sort()
r = dict()
for i in range(k):
	r[s[i]] = i
ans = bfs()
print(*ans)


from collections import *
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)[::-1]
f = sum(b[:k])
f1 = Counter(b[:k])
r = []
s = 0
for i in range(n):
	s += 1
	if a[i] in f1:
		if f1[a[i]] > 0:
			r.append(s)
			s = 0
			f1[a[i]] -= 1
		else:
			pass
print(f)
if sum(r) != n:
	r[-1] += n - sum(r)
print(*r)


(n, k) = map(int, input().split())
temp = [int(x) for x in input().split()]
line = list(zip(temp, range(1, n + 1)))
line.sort(key=lambda x: x[0], reverse=True)
l = line[:k]
l.sort(key=lambda x: x[1])
s = l[0][0]
ans = [l[0][1]]
for i in range(1, k):
	s += l[i][0]
	ans.append(l[i][1] - l[i - 1][1])
ans[-1] = ans[-1] + n - l[-1][1]
print(s)
print(*ans)


(n, k) = [int(i) for i in input().split()]
p = [(int(v), i) for (i, v) in enumerate(input().split())]
p = sorted(p, key=lambda student: -student[0])
a = []
for i in range(k):
	a.append(p[i])
a.append((0, n))
a = sorted(a, key=lambda student: student[1])
print(sum([pair[0] for pair in a]))
x = []
start = 0
for i in range(k - 1):
	x.append(str(a[i][1] - start + 1))
	start = a[i][1] + 1
x.append(str(n - start))
print(' '.join(x))


(n, k) = input().split(' ')
n = int(n)
k = int(k)
arr = input().split(' ')
new = [int(i) for i in arr]
arr = [int(i) for i in arr]
new.sort(reverse=True)
new = new[0:k]
print(sum(new))
c = 0
x = 0
m = len(new)
for i in arr:
	c += 1
	if i in new and x < 1:
		x += 1
		new.remove(i)
	elif x >= 1 and x < m:
		if i in new:
			new.remove(i)
			print(c - 1, end=' ')
			c = 1
print(c)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
	A[i] = (A[i], i + 1)
A = sorted(A, reverse=True)
Total = 0
List = [0, N]
for i in range(K):
	Total += A[i][0]
	List += [A[i][1]]
List = sorted(List)
del List[-2]
AnsList = ''
for i in range(K):
	AnsList += str(List[i + 1] - List[i]) + ' '
print(Total)
print(AnsList)


a = input().split()
b = input().split()
for i in range(int(a[0])):
	b[i] = int(b[i])
c = b
c = sorted(c)
c = c[-int(a[1]):]
print(sum(c))
ile = 1
ans = []
for i in range(int(a[0])):
	if b[i] in c:
		if len(c) == 1:
			ans.append(ile + (int(a[0]) - i - 1))
		else:
			ans.append(ile)
		ile = 0
		c.remove(b[i])
	ile += 1
print(*ans)


(n, k) = input().split()
n = int(n)
k = int(k)
list1 = [int(x) for x in input().split()]
index = []
maxis = []
for i in range(k):
	temp = max(list1)
	maxis.append(temp)
	temp2 = list1.index(temp)
	index.append(temp2)
	list1[temp2] = -1
print(sum(maxis))
index.sort()
counter = 1
flag = 0
for i in range(len(list1)):
	if flag == k - 1:
		print(n - i)
		break
	if i in index:
		print(counter, end=' ')
		flag += 1
		counter = 1
	else:
		counter += 1


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
t = sorted(a)[-k]
f = [False] * n
cnt = 0
for i in range(n):
	if a[i] > t:
		f[i] = True
		cnt += 1
for i in range(n):
	if a[i] == t:
		f[i] = True
		cnt += 1
		if cnt == k:
			break
ans = 0
pre = -1
index = []
cnt = 0
for i in range(n):
	if f[i]:
		cnt += 1
		ans += a[i]
		index.append(i - pre)
		pre = i
print(ans)
index.pop()
index.append(n - sum(index))
print(*index)


(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
inds = list(range(1, n + 1))
inds.sort(key=lambda x: arr[x - 1], reverse=True)
max_inds = inds[:k]
max_inds.sort()
total = sum([arr[i - 1] for i in max_inds])
max_inds[-1] = n
for i in range(k - 1, 0, -1):
	max_inds[i] -= max_inds[i - 1]
print(total)
print(*max_inds)


def mi():
	return map(int, input().split())
(n, k) = mi()
a = list(mi())
for i in range(n):
	a[i] = [a[i], i]
a.sort(reverse=True)
a = a[:k]
s = 0
ind = []
for i in a:
	s += i[0]
	ind.append(i[1])
ind.sort()
for i in range(k):
	ind[i] += 1
ind1 = ind.copy()
for i in range(1, len(ind)):
	ind[i] -= ind1[i - 1]
ind[-1] = n - sum(ind[:k - 1])
print(s)
for i in ind:
	print(i, end=' ')


from sys import stdin
input = stdin.buffer.readline
(n, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
l = []
for i in range(n):
	l.append((arr[i], i))
l.sort(reverse=True)
dp = []
x = 0
for i in range(k):
	dp.append(l[i][1])
	x = x + l[i][0]
print(x)
dp.sort()
dp = [-1] + dp
l = len(dp)
for i in range(1, l - 1):
	print(dp[i] - dp[i - 1], end=' ')
print(n - 1 - dp[l - 2])


(n, k) = map(int, input().split())
l = [int(x) for x in input().split()]
index_l = [i for i in range(len(l))]
z = [x for (_, x) in sorted(zip(l, index_l), reverse=True)]
y = [x for (x, _) in sorted(zip(l, index_l), reverse=True)]
ip = []
i = 0
total_sum = 0
while i < k and i < n:
	ip.append(z[i] + 1)
	total_sum += y[i]
	i += 1
ip.append(0)
ip = sorted(ip)
ip.pop()
ip.append(n)
print(total_sum)
for i in range(1, len(ip)):
	print(ip[i] - ip[i - 1], end=' ')


(n, t) = map(int, input().split())
a = [int(i) for i in input().split()]
b = a[:]
b.sort(reverse=True)
c = b[:t]
today = 0
date = []
print(sum(c))
for i in range(n):
	today += 1
	if len(date) == t - 1:
		date.append(str(n - sum(date)))
		break
	if a[i] in c:
		c.remove(a[i])
		date.append(today)
		today = 0
print(' '.join([str(i) for i in date]))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list()
for i in range(n):
	b.append((a[i], i + 1))
b.sort()
c = list()
sum = 0
for elem in b[-k:]:
	c.append(elem[1])
	sum += elem[0]
c.sort()
print(sum)
pred = 0
for i in range(k - 1):
	print(c[i] - pred, end=' ')
	pred = c[i]
print(n - pred)


mod = 10 ** 9 + 7
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
(n, k) = f()
l = [[j, i] for (i, j) in enumerate(il())]
l.sort(reverse=True)
l2 = [l[i][1] for i in range(k)]
sm = sum((l[i][0] for i in range(k)))
l2.sort()
l2[-1] = n - 1
l2 = [-1] + l2
print(sm)
for i in range(1, k + 1):
	print(l2[i] - l2[i - 1], end=' ')


class X:

	def __init__(self, ind=0, val=0):
		self.ind = ind
		self.val = val
(n, m) = map(int, input().split())
num = list(map(int, input().split()))
ans = []
for (ind, val) in enumerate(num):
	ans.append(X(ind, val))
ans.sort(key=lambda x: x.val, reverse=True)
print(sum((ans[i].val for i in range(m))))
mp = [X(n)]
for i in range(m):
	mp.append(ans[i])
mp.sort(key=lambda x: x.ind)
ans = []
ji = 0
for i in range(1, len(mp)):
	ans.append(mp[i].ind - ji)
	ji = mp[i].ind
print(' '.join((str(i) for i in ans)))


(n, k) = map(int, input().strip().split(' '))
lst = list(map(int, input().strip().split(' ')))
l = []
l[:] = lst[:]
l.sort(reverse=True)
l = l[:k]
print(sum(l))
c = []
j = 0
c1 = 0
for i in range(n):
	if j == k - 1:
		c.append(n - i)
		break
	elif lst[i] in l:
		c1 += 1
		c.append(c1)
		del l[l.index(lst[i])]
		j += 1
		c1 = 0
	else:
		c1 += 1
for j in range(len(c)):
	print(c[j], end=' ')


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l1 = sorted(enumerate(l), key=lambda x: -x[1])[:k]
ans = 0
for (i, x) in enumerate(l1):
	ans += x[1]
l1.sort()
l2 = []
print(ans)
pre = -1
for (i, x) in enumerate(l1[:-1]):
	l2.append(x[0] - pre)
	pre = x[0]
l2.append(len(l) - 1 - pre)
print(*l2)


(n, m) = map(int, input().split())
ls = list(map(int, input().split()))
sls = list(sorted(ls, reverse=True))
ans = 0
lss = []
rls = []
for i in range(m):
	ans += sls[i]
	lss.append(sls[i])
c = 0
if m == 1:
	print(ans)
	print(n)
	exit()
for i in range(n):
	c += 1
	if ls[i] in lss:
		rls.append(c)
		del lss[lss.index(ls[i])]
		if len(rls) == m - 1:
			rls.append(n - sum(rls))
			break
		c = 0
print(ans)
print(*rls)


from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
(n, k) = mi()
a = li()
b = []
for i in range(n):
	b.append([a[i], i + 1])
b.sort(reverse=True)
c = []
ans = 0
for i in range(k):
	ans += b[i][0]
	c.append(b[i][1])
print(ans)
c.sort()
c[k - 1] = n
a = []
s = 0
for i in range(k):
	a.append(c[i] - s)
	s = c[i]
print(*a)


(z, zz) = (input, lambda : map(int, z().split()))
(n, k) = zz()
l = sorted(zip(zz(), range(n)))[-k:]
print(sum((i[0] for i in l)))
p = sorted((i[1] for i in l)) + [n]
p[0] = 0
for (x, y) in zip(p, p[1:]):
	print(y - x, end=' ')


(n, k) = map(int, input().split())
pro = [int(i) for i in input().split()]
maxes = sorted(pro, reverse=True)
keys = {}
tot = 0
indexes = []
for i in range(k):
	if maxes[i] in keys:
		keys[maxes[i]] += 1
	else:
		keys[maxes[i]] = 1
for i in keys.keys():
	tot += keys[i] * i
	for j in range(n):
		if keys[i] == 0:
			break
		if pro[j] == i:
			if keys[i] >= 1:
				keys[i] -= 1
				indexes.append(j + 1)
indexes.sort()
print(tot)
if k == 1:
	print(n)
else:
	for i in range(k - 1):
		if i == 0:
			print(indexes[i + 1] - 1, end=' ')
		else:
			print(indexes[i + 1] - indexes[i], end=' ')
	print(n + 1 - indexes[-1])


(m, n) = map(int, input().split())
l = list(map(int, input().split()))
cn = list(enumerate(l, 0))
cn.sort(key=lambda x: -x[1])
print(sum([cn[i][1] for i in range(n)]))
day = [-1] + sorted([cn[i][0] for i in range(n)]) + [m]
for i in range(1, n):
	print(day[i] - day[i - 1], end=' ')
print(m - 1 - day[n - 1])


(n, k) = list(map(int, input().split()))
l = list(map(int, input().split()))
ans = 0
an1 = []
sums = []
li = l.copy()
l.sort(reverse=True)
for i in range(k):
	ans += l[i]
	an1.append(l[i])
for i in range(n):
	if len(an1) == 1:
		sums.append(n - sum(sums))
		break
	if li[i] in an1:
		sums.append(i + 1 - sum(sums))
		an1.remove(li[i])
print(ans)
print(' '.join(map(str, sums)))


from sys import stdin, stdout
input = lambda : stdin.readline().rstrip()
write = stdout.write

def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if K == 1:
		print(max(A))
		print(N)
		return
	a = sorted(A, reverse=1)
	(num, profit) = ([0], 0)
	for i in range(K):
		profit += a[i]
		j = A.index(a[i])
		num.append(j + 1)
		A[j] = 0
	num.sort()
	num[-1] += N - num[-1]
	print(profit)
	print(*[num[i + 1] - num[i] for i in range(K)])
main()


def poleznost(lst, n, k):
	b = list()
	for i in range(len(lst)):
		b.append(tuple([lst[i], i]))
	d = sorted(b, key=lambda x: x[0])
	s = 0
	z = [-1]
	for elem in sorted(d[len(d) - 1:-k - 1:-1], key=lambda y: y[1]):
		z.append(elem[1])
		s += elem[0]
	z[len(z) - 1] = n - 1
	m = list()
	for i in range(1, len(z)):
		m.append(z[i] - z[i - 1])
	return (s, m)
(n, k) = [int(j) for j in input().split()]
a = [int(i) for i in input().split()]
print(poleznost(a, n, k)[0])
print(*poleznost(a, n, k)[1])


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if k == 1:
	print(max(a))
	print(n)
else:
	idx = sorted(range(len(a)), key=lambda x: a[x])[-k:]
	tmp_counter = 0
	perm = []
	power = 0
	for i in range(n):
		tmp_counter += 1
		if i in idx:
			perm.append(tmp_counter)
			tmp_counter = 0
			power += a[i]
	perm[-1] = n - sum(perm[:k - 1])
	print(power)
	for i in range(k):
		print(perm[i], end=' ')


[n, k] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
di = {}
for i in range(n):
	if A[i] in di:
		di[A[i]].append(i)
	else:
		di[A[i]] = [i]
B = sorted(A)
pos = []
count = 0
for i in sorted(di.keys(), reverse=True):
	for j in di[i]:
		pos.append(j)
		count += 1
		if count == k:
			break
	if count == k:
		break
pos.sort()
sum = 0
for i in pos:
	sum += A[i]
print(sum)
diff = 0
ans = []
for i in pos:
	ans.append(i - diff + 1)
	diff = i + 1
ans[-1] += n - diff
for i in ans:
	print(i, end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a_s = sorted(enumerate(a), key=lambda x: x[1], reverse=True)
a_s2 = sorted(a_s[:k], key=lambda x: x[0])
ac = 0
b = []
first = True
p = 0
val = 0
if k > 1:
	for (i, j) in a_s2:
		if not first:
			b.append(i - p)
			p = i
		else:
			first = False
		ac += j
		val = i
else:
	ac = a_s2[0][1]
b.append(n - val)
print(ac)
print(' '.join(map(str, b)))


(n, k) = map(int, input().split())
L = list(map(int, input().split()))
masum = 0
while k > 0:
	ma = max(L)
	for a in range(len(L)):
		if L[a] == ma and k > 0:
			masum += ma
			k -= 1
			L[a] = -1
A = []
c = 0
for a in range(len(L)):
	if L[a] == -1:
		A.append(a - c + 1)
		c = a + 1
A[-1] = A[-1] + (len(L) - sum(A))
print(masum)
print(' '.join(map(str, A)))


(n, k) = map(int, input().split())
list = [int(i) for i in input().split()]
temp1 = list.copy()
temp1.sort(reverse=True)
som = 0
temp2 = []
for i in range(0, k):
	temp2.append(list.index(temp1[i]))
	list[list.index(temp1[i])] = -1
for i in range(0, k):
	som += temp1[i]
print(som)
temp2.sort()
if k != 1:
	print(temp2[0] + 1, end=' ')
	for i in range(1, k - 1):
		print(temp2[i] - temp2[i - 1], end=' ')
	print(n - temp2[k - 2] - 1)
else:
	print(n)


def getMaxProfit(n, k, problems):
	if k == 1:
		return str(max(problems)) + '\n' + str(n)
	max_indices = {}
	max_profit = 0
	for i in range(k):
		curr_max = 0
		while max_indices.get(curr_max) is not None:
			curr_max += 1
		for j in range(curr_max, n):
			if max_indices.get(j) is None and problems[j] > problems[curr_max]:
				curr_max = j
		max_profit += problems[curr_max]
		max_indices[curr_max] = True
	max_indices = list(max_indices.keys())
	max_indices.sort()
	problems_size = str(max_indices[1]) + ' '
	for i in range(1, len(max_indices) - 1):
		problems_size += str(max_indices[i + 1] - max_indices[i]) + ' '
	problems_size += str(n - max_indices[len(max_indices) - 1])
	return str(max_profit) + '\n' + problems_size
(n, k) = input().split()
problems = [int(x) for x in input().split()]
print(getMaxProfit(int(n), int(k), problems))


(n, d) = map(int, input().split())
ai = list(map(int, input().split()))
arr = sorted(ai, reverse=True)[:d]
s = sum(arr)
lst = []
last = -1
i = 0
while len(arr) > 0:
	if ai[i] in arr:
		lst.append(i - last)
		last = i
		arr.remove(ai[i])
	i += 1
lst[-1] += len(ai) - i
print(s)
print(*lst)


(n, k) = map(int, input().split())
v = [*map(int, input().split())]
a = sorted(v, reverse=True)
vis = [0] * 2002
t = []
ans = 0
num = 0
ff = False
for i in range(k):
	vis[a[i]] += 1
for i in range(n):
	f = False
	for j in range(k):
		if a[j] == v[i] and vis[a[j]]:
			vis[a[j]] -= 1
			f = True
			ans += a[j]
			if len(t) == k - 1:
				t.append(n - i + num)
				ff = True
				break
			num += 1
			t.append(num)
			num = 0
			break
	if f == False:
		num += 1
	if ff:
		break
print(ans)
for i in t:
	print(i, end=' ')


(n, k) = map(int, input().split())
l = [int(x) for x in input().split()]
z = l[:]
z.sort()
print(sum(z[n - k:]))
o = []
for i in range(k):
	o.append(z[n - k + i])
p = 0
for i in range(n):
	if l[i] in o and len(o) > 1:
		print(p + 1, end=' ')
		p = 0
		o.remove(l[i])
	elif i == n - 1:
		p += 1
		print(p)
	else:
		p += 1


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
X = [(A[ind], ind) for ind in range(n)]
X.sort(reverse=True)
USE = [0] * n
SUM = 0
for i in range(k):
	SUM += X[i][0]
	USE[X[i][1]] = 1
ANS = []
NOW = -1
for i in range(n):
	if USE[i] == 1:
		ANS.append(i - NOW)
		NOW = i
ANS[-1] += n - NOW - 1
print(SUM)
print(*ANS)


(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
b = sorted(a)
b.reverse()
mx = []
for i in range(k):
	mx.append(b[i])
p = []
s = 0
counter = 0
for i in range(n):
	if k > 0 and a[i] in mx:
		mx.remove(a[i])
		p.append(i - counter + 1)
		counter = i + 1
		s += a[i]
		k -= 1
print(s)
if sum(p) < n:
	last = len(p) - 1
	s = sum(p) - p[last]
	p[last] = n - s
print(*p)


def practice(arr, days, n):
	values = sorted(arr)[n - days:]
	maximum_sum = sum(values)
	ans = []
	count = 0
	if days == 1:
		return [max(arr), [n]]
	else:
		for x in arr:
			count += 1
			if x in values and len(values) > 1:
				values.remove(x)
				ans.append(count)
				count = 0
		ans.append(count)
	return [maximum_sum, ans]
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
ans = practice(arr, k, n)
print(ans[0])
print(*ans[1])


from collections import Counter
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=1)[:k]
print(sum(b))
b = Counter(b)
res = []
for i in range(n):
	if a[i] in b and b[a[i]]:
		b[a[i]] -= 1
		res.append(i + 1)
res[-1] = n
for i in range(k - 2, -1, -1):
	res[i + 1] -= res[i]
print(*res)


from sys import stdin
from math import *

def h(seq):
	return sorted(range(len(seq)), key=seq.__getitem__)
line = stdin.readline().rstrip().split()
m = int(line[0])
k = int(line[1])
numbers = list(map(int, stdin.readline().rstrip().split()))
arrNum = h(numbers)
positions = list(reversed(arrNum))[:k]
positions.sort()
total = 0
oldPosition = -1
l = []
index = 1
for n in positions:
	extra = 0
	if index == k:
		extra = m - n - 1
	l.append(n - oldPosition + extra)
	total += numbers[n]
	oldPosition = n
	index += 1
print(total)
for n in l:
	print(n, end=' ')


from sys import stdin
from collections import *

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])
(n, k) = arr_inp(1)
(a, ans, tem, s) = (arr_inp(1), [], 0, 0)
maxes = Counter((i for i in sorted(a.copy(), reverse=True)[:k]))
for i in range(n):
	tem += 1
	if maxes[a[i]]:
		maxes[a[i]] -= 1
		k -= 1
		s += a[i]
		if k:
			ans.append(tem)
			tem = 0
ans.append(tem)
print(s)
print(*ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
p = sorted(a)
p = p[-k:]
s = sum(p)
print(s)
idx = 0
i = 0
count = 0
ans = []
while len(ans) < k - 1:
	idx += 1
	count += 1
	if a[i] in p:
		p.remove(a[i])
		ans.append(count)
		count = 0
	i += 1
for i in ans:
	print(i, end=' ')
print(n - idx)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
kbig = sorted(a, reverse=True)[:k]
print(sum(kbig))
lout = []
c = 0
s = 0
for i in range(n):
	if len(lout) == k - 1:
		lout.append(n - s)
		break
	c += 1
	if a[i] in kbig:
		lout.append(c)
		kbig.remove(a[i])
		s += c
		c = 0
for e in lout:
	print(e, end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
	print(max(a))
	print(n)
else:
	b = []
	u = int()
	cnt = int()
	for i in range(k):
		u = max(a)
		cnt += u
		b.append(a.index(u))
		a[b[i]] = 0
	b.sort()
	print(cnt)
	print(b[0] + 1, end=' ')
	for i in range(1, k - 1):
		print(b[i] - b[i - 1], end=' ')
	print(n - b[k - 2] - 1)


(n, k) = map(int, input().split())
m = list(map(int, input().split()))
s = m + [0]
s.pop()
s.sort()
r = s[n - k:n]
print(sum(r))
g = [False] * n
for elem in r:
	for i in range(n):
		if not g[i] and m[i] == elem:
			g[i] = True
			break
count = 0
al = []
for i in range(n):
	if g[i] == True:
		count += 1
		al += [count]
		count = 0
	else:
		count += 1
k = len(al) - 1
al[k] += count
for i in range(k + 1):
	print(al[i], end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append((a[i], i))
b.sort(reverse=True)
temp = []
ans = 0
for i in range(k):
	temp.append(abs(b[i][1]))
	ans += b[i][0]
temp.sort()
if k > 1:
	c = [temp[0] + 1]
	for i in range(1, len(temp) - 1):
		c.append(temp[i] - temp[i - 1])
	c.append(n - temp[-2] - 1)
else:
	c = [n]
print(ans)
print(*c)


def solve(n, k, a):
	if k == 1:
		print(max(a))
		print(n)
		return 0
	p = sorted(a)[n - k:n]
	ind = []
	ind = [a.index(p[0])]
	for i in range(1, k):
		if p[i] == p[i - 1]:
			ind.append(a.index(p[i - 1], ind[i - 1] + 1, n))
		else:
			ind.append(a.index(p[i]))
	ind = sorted(ind)
	ans = [ind[0] + 1]
	for j in range(1, k - 1):
		ans.append(ind[j] - ind[j - 1])
	ans.append(n - sum(ans))
	print(sum(p))
	print(*ans)
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
solve(n, k, a)


import sys
readline = sys.stdin.readline
from collections import Counter
(N, K) = map(int, readline().split())
A = list(map(int, readline().split()))
B = A[:]
B.sort(reverse=True)
B = B[:K]
ans = sum(B)
B = Counter(B)
table = [0] * N
for i in range(N):
	if B[A[i]]:
		B[A[i]] -= 1
		table[i] = 1
l = []
cnt = 0
for i in range(N):
	cnt += 1
	if table[i]:
		l.append(cnt)
		cnt = 0
l[-1] += N - sum(l)
print(ans)
print(*l)


func = lambda : map(int, input().split())
(n, k) = func()
l = sorted(zip(func(), range(n)))[-k:]
print(sum((x[0] for x in l)))
b = sorted((x[1] for x in l)) + [n]
b[0] = 0
print(*(b - a for (a, b) in zip(b, b[1:])))


def indexes(arr, num, key):
	cou = []
	for i in range(len(arr)):
		if len(cou) < num and a[i] == key:
			cou.append(i + 1)
	return cou
(n, k) = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]
b = sorted(a)
c = b[n - k:]
ans = sum(c)
l = []
for i in range(len(c)):
	if i == len(c) - 1 or c[i] != c[i + 1]:
		l.extend(indexes(a, c.count(c[i]), c[i]))
l = sorted(l)
print(ans)
l[-1] = n
print(l[0], end=' ')
for i in range(1, len(l)):
	print(l[i] - l[i - 1], end=' ')


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
s1 = []
s1 = []
for i in range(n):
	s1.append([s[i], i])
s1.sort()
s1 = s1[::-1]
s2 = [-1]
p = 0
for i in range(m):
	p += s1[i][0]
	s2.append(s1[i][1])
print(p)
s2.sort()
s2[-1] = n - 1
for i in range(1, len(s2)):
	print(s2[i] - s2[i - 1], end=' ')


(n, l) = list(map(int, input().split()))
pop = list(map(int, input().split()))
kam = []
lo = []
som = []
to = []
for item in pop:
	kam.append(item)
if l == 1:
	print(max(pop))
	print(len(pop))
else:
	for x in range(l):
		man = pop.index(max(pop))
		lo.append(man)
		to.append(pop[man])
		pop[man] = -5
	lo.sort()
	print(sum(to))
	y = 0
	for x in range(len(lo)):
		if x != len(lo) - 1:
			som.append(len(kam[y:lo[x] + 1]))
			y = lo[x] + 1
		else:
			som.append(n - sum(som))
	print(*som)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
if k == 1:
	print(max(arr))
	print(n)
	exit()
arr = [[arr[i], i] for i in range(n)]
arr = sorted(arr, reverse=True, key=lambda x: x[0])
tmp = []
ans = 0
for i in range(k):
	(v, pos) = arr[i]
	ans += v
	tmp.append(pos)
tmp = sorted(tmp)
ans2 = []
for i in range(k - 1):
	if i == 0:
		ans2.append(tmp[i] + 1)
	else:
		ans2.append(tmp[i] - tmp[i - 1])
ans2.append(n - tmp[-2] - 1)
print(ans)
print(*ans2)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
P = []
for (i, v) in enumerate(a):
	P.append((v, i))
P = sorted(P, reverse=True)
a = sorted(a, reverse=True)
P = P[:k]
s = sum(a[:k])
P = sorted(P, key=lambda x: x[1])
rec = []
las = 0
for i in range(k - 1):
	rec.append(P[i][1] - las + 1)
	las = P[i][1] + 1
rec.append(n - las)
print(s)
print(*rec)


from operator import itemgetter

def mir():
	return map(int, input().split(' '))
(n, k) = mir()
aa = mir()
pp = sorted(enumerate(aa), reverse=True, key=itemgetter(1))[:k]
s = sum(map(itemgetter(1), pp))
pp = sorted(pp) + [(n,)]
rr = [pp[i + 1][0] - pp[i][0] for i in range(k)]
rr[0] += pp[0][0]
print(s)
print(*rr)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
p = list(l)
p.sort()
q = [p[i] for i in range(n - 1, n - k - 1, -1)]
t = sum(q)
for i in range(n):
	if l[i] in q:
		z = l[i]
		l[i] = 0
		q.remove(z)
c = 0
y = []
for i in range(n):
	if l[i] == 0:
		y.append(i + 1)
y[0] = 1
y.append(n + 1)
print(t)
u = []
for j in range(len(y) - 1):
	u.append(y[j + 1] - y[j])
print(*u)


from __future__ import print_function
from bisect import bisect_left, bisect_right, insort
from collections import Sequence, MutableSequence
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
from functools import wraps
from sys import hexversion
if hexversion < 50331648:
	from itertools import imap as map
	from itertools import izip as zip
	try:
		from thread import get_ident
	except ImportError:
		from dummy_thread import get_ident
else:
	from functools import reduce
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				if start_pos == stop_pos:
					return _lists[start_pos][start_idx:stop_idx]
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(range(min_idx, max_idx))
				return map(_lists[min_pos].__getitem__, indices)
			indices = range(min_idx, max_idx)
			return map(_lists[min_pos].__getitem__, indices)
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = range(min_idx, len(_lists[min_pos]))
				max_indices = range(max_idx)
				return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
			min_indices = range(min_idx, len(_lists[min_pos]))
			max_indices = range(max_idx)
			return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
		if reverse:
			min_indices = range(min_idx, len(_lists[min_pos]))
			sublist_indices = range(next_pos, max_pos)
			sublists = map(_lists.__getitem__, reversed(sublist_indices))
			max_indices = range(max_idx)
			return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
		min_indices = range(min_idx, len(_lists[min_pos]))
		sublist_indices = range(next_pos, max_pos)
		sublists = map(_lists.__getitem__, sublist_indices)
		max_indices = range(max_idx)
		return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n        Comparisons use lexicographical order as with sequences.\n        Runtime complexity: `O(n)`\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			import sys
			import traceback
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

def identity(value):
	return value
(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
p = SortedList(a)
p = p[-k:]
print(sum(p))
count = 0
outercount = 0
i = 0
ans = []
s = 0
while i != n and outercount < k - 1:
	count += 1
	s += 1
	if a[i] in p:
		p.remove(a[i])
		outercount += 1
		ans.append(count)
		count = 0
	i += 1
for elem in ans:
	print(elem, end=' ')
print(n - s)


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = []
for i in a:
	b.append(i)
b.sort(reverse=True)
res = []
last = 0
count = []
for i in range(k):
	res.append(b[i])
print(sum(res))
for i in range(n):
	if a[i] in res:
		count.append(i + 1 - last)
		res.remove(a[i])
		last = i + 1
if sum(count) < n:
	count[-1] += n - sum(count)
print(*count, sep=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
b = b[:k]
s = sum(b)
rec = []
k = 1
for i in range(n):
	if a[i] not in b:
		k += 1
		continue
	else:
		b.remove(a[i])
		rec.append(k)
		k = 1
rec[-1] += n - sum(rec)
print(s)
print(' '.join(map(str, rec)))


R = lambda : map(int, input().split())
(n, k) = R()
arr = [[int(x)] for x in input().split()]
if k == 1:
	print(max(arr)[0], '\n', n)
else:
	for i in range(n):
		arr[i].append(i)
	arr.sort(reverse=True)
	brr = []
	s = 0
	for i in range(k):
		s += arr[i][0]
		brr.append(arr[i])
	brr.sort(key=lambda e: e[1])
	print(s)
	print(brr[0][1] + 1, end=' ')
	for i in range(1, k - 1):
		print(brr[i][1] - brr[i - 1][1], end=' ')
	if k != 1:
		print(n - brr[-2][1] - 1, end=' ')


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
b = [(arr[i], i) for i in range(n)]
b.sort(reverse=True)
index = []
for i in range(k):
	index.append(b[i][1])
index.sort()
index.pop()
index.append(n - 1)
ans = 0
for i in range(k):
	ans += b[i][0]
print(ans)
pre = -1
ans_1 = []
for i in index:
	ans_1.append(i - pre)
	pre = i
for i in range(len(ans_1)):
	print(ans_1[i], end=' ')
print()


(n, k) = [int(__) for __ in input().strip().split()]
arr = [int(__) for __ in input().strip().split()]
co = arr[:]
arr.sort()
arr = arr[::-1]
ans = 0
dic = {}
for i in range(k):
	ans += arr[i]
	if arr[i] in dic:
		dic[arr[i]] += 1
	else:
		dic[arr[i]] = 1
print(ans)
count = 1
for i in range(n):
	if co[i] in dic and dic[co[i]] >= 1 and (k > 1):
		print(count, end=' ')
		dic[co[i]] -= 1
		k -= 1
		count = 0
	elif i == n - 1:
		print(count)
	count += 1


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
l = range(n)
t = sorted(zip(a, l))
a = [x for (x, y) in t][n - k:]
l = [y for (x, y) in t][n - k:]
print(sum(a))
l.sort()
cnt = -1
tl = []
for i in l:
	tl.append(i - cnt)
	cnt = i
if k == 1:
	print(n)
else:
	tl[-1] = n - 1 - l[-2]
	print(*tl)


(n, k) = map(int, input().strip().split(' '))
arr = list(map(int, input().strip().split(' ')))
ans = []
for i in range(n):
	p = [arr[i], i * -1]
	ans.append(p)
ans.sort(reverse=True)
tot = 0
lol = []
for i in range(k):
	tot += ans[i][0]
	lol.append(ans[i][1] * -1)
lol.sort()
if k == 1:
	print(max(arr))
	print(n)
else:
	print(tot)
	print(lol[0] + 1, end=' ')
	for i in range(1, k - 1):
		print(lol[i] - lol[i - 1], end=' ')
	print(n - 1 - lol[k - 2])


(n, k) = [int(x) for x in input().split()]
dif = [int(x) for x in input().split()]
top = []
sum = 0
count = []
for _ in range(k):
	ind = dif.index(max(dif))
	sum += max(dif)
	dif[ind] = 0
	top.append(ind)
l = 0
r = dif.index(0)
for _ in range(k - 1):
	count.append(len(range(l, r + 1)))
	dif[r] = -1
	l = r + 1
	r = dif.index(0)
count.append(len(range(l, n)))
print(sum)
print(*count)


(countNumbers, countSplit) = [int(num) for num in input().split()]
numbers = [int(num) for num in input().split()]
values = [0] * countSplit
pos = [-1] * countSplit
countFind = 0
for index in range(countNumbers):
	if countFind < countSplit:
		values[countFind] = numbers[index]
		pos[countFind] = index
		countFind += 1
	else:
		m = min(values)
		if numbers[index] > m:
			for ind in range(countFind):
				if values[ind] == m:
					values[ind] = numbers[index]
					pos[ind] = index
					break
print(sum(values))
if countSplit == 1:
	print(countNumbers)
else:
	pos.sort()
	print(pos[0] + 1, end=' ')
	for index in range(1, countFind - 1):
		print(pos[index] - pos[index - 1], end=' ')
	print(countNumbers - pos[countFind - 2] - 1)


import heapq
(N, K) = map(int, input().split())
A = [int(i) for i in input().split()]
B = sorted(A, reverse=True)[:K]
print(sum(B))
res = []
prev = 0
for (ind, elem) in enumerate(A):
	if len(B) == 1:
		res.append(N - ind)
		break
	if elem in B:
		res.append(ind + 1 - prev)
		prev = ind + 1
		B.remove(elem)
print(*res)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
need = sorted(a, reverse=True)
ind = list()
for el in need[:k]:
	ind.append(a.index(el))
	a[a.index(el)] = 0
ind.sort()
print(sum(need[:k]))
ind[-1] = n - 1
ind.insert(0, -1)
ans = [el - ind[i] for (i, el) in enumerate(ind[1:])]
print(' '.join(map(str, ans)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [(a[i], i) for i in range(n)]
b.sort(reverse=True)
ind = []
for i in range(k):
	ind.append(b[i][1])
ind.sort()
ind.pop()
ind.append(n - 1)
res = 0
for i in range(k):
	res += b[i][0]
print(res)
prev = -1
for i in ind:
	print(i - prev, end=' ')
	prev = i


(n, k) = map(int, input().strip().split())
q = list(map(int, input().strip().split()))
q1 = sorted(q)
q1.reverse()
ta = q1[:k]
su = sum(q1[:k])
t = []
t1 = 1
if k == 1:
	print(max(q))
	print(len(q))
else:
	for i in range(n):
		if q[i] in ta:
			ta[ta.index(q[i])] = -1
			t.append(t1)
			if len(t) == k - 1:
				t.append(n - i - 1)
				break
			t1 = 1
		else:
			t1 += 1
	print(su)
	print(*t)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if k == 1:
	print(max(a))
	print(n)
else:
	p = []
	for j in range(n):
		p.append([a[j], j])
	p.sort()
	p = p[-1:-k - 1:-1]
	p = sorted(p, key=lambda x: x[1])
	s = 0
	y = []
	for j in range(k):
		s += p[j][0]
		if j == 0:
			y.append(p[j][1] + 1)
		elif j != k - 1:
			y.append(p[j][1] - p[j - 1][1])
		else:
			y.append(n - p[j - 1][1] - 1)
	print(s)
	print(*y)


a = int(input().split()[1])
z = list(map(int, input().split()))
s = 0
r = [0]
while a:
	s += max(z)
	r += [z.index(max(z)) + 1]
	z[z.index(max(z))] = -1
	a -= 1
print(s)
s = 0
r = sorted(r)
r[-1] = len(z)
for i in range(1, len(r)):
	print(r[i] - r[i - 1], end=' ')


(c, d) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(d):
	m = -1
	for j in range(c):
		if a[j] > m:
			m = a[j]
			n = j
	a[n] = 0
	ans += m
count = 0
print(ans)
for i in range(c):
	count += 1
	if a[i] == 0 and d > 1:
		print(count, end=' ')
		count = 0
		d -= 1
print(count)


from sys import stdin, stdout
from heapq import heappush, heappop
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(1):
	(n, k) = lst()
	a = lst()
	biggest = []
	l = sorted([[a[i], i] for i in range(n)], reverse=1)
	ind = set([i for (j, i) in l[:k]])
	ans = []
	cnt = 1
	mx = 0
	for i in range(n):
		if i in ind:
			ans += [cnt]
			mx += a[i]
			cnt = 1
		else:
			cnt += 1
	print(mx)
	ans[-1] += n - sum(ans)
	print(*ans)


H = input().split()
n = int(H[0])
k = int(H[1])
A = list(map(int, input().split()))
ans = 0
B = []
if k == 1:
	print(max(A))
	print(n)
else:
	for i in range(k):
		ans += max(A)
		t = A.index(max(A))
		B.append(t + 1)
		A[t] = 0
		B.sort()
	B[0] = B[1] - 1
	for i in range(1, k - 1):
		B[i] = B[i + 1] - B[i]
	B[k - 1] = n + 1 - B[k - 1]
	print(ans)
	for elem in B:
		print(elem, end=' ')


import heapq

def max_profit(arr, n, k):
	klargest = heapq.nlargest(k, arr)
	print(sum(klargest))
	size = 0
	result = []
	for c in arr:
		if c in klargest:
			klargest.remove(c)
			result.append(size + 1)
			size = 0
		else:
			size += 1
	result[-1] += size
	print(*result)
(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
max_profit(arr, n, k)


import math

def main():
	(n, k) = list(map(int, input().split()))
	li1 = list(map(int, input().split()))
	li = sorted(li1, reverse=True)
	di = dict()
	for i in range(k):
		if li[i] in di:
			di[li[i]] += 1
		else:
			di[li[i]] = 1
	res = []
	count = 0
	for i in range(len(li1)):
		if li1[i] in di.keys() and di[li1[i]] > 0:
			res.append(i + 1 - count)
			count = i + 1
			di[li1[i]] -= 1
	res[k - 1] = len(li1) - (sum(res) - res[k - 1])
	sum1 = 0
	for i in range(k):
		sum1 += li[i]
	print(sum1)
	for i in res:
		print(i, end=' ')
	print()
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(0, n):
	b.append([a[i], i])
b.sort()
b.reverse()
ans = 0
v = [0]
for i in range(0, k):
	v.append(b[i][1] + 1)
	ans += b[i][0]
v.sort()
print(ans)
for i in range(1, k):
	print(v[i] - v[i - 1], end=' ')
print(n - v[k - 1])


nm = list(map(int, input().split(' ')))
n = nm[0]
k = nm[1]
a = list(map(int, input().split(' ')))
max = [0 for i in range(k)]
dist = [0 for i in range(k)]
min = 2001
for i in range(k):
	max[i] = a[i]
	dist[i] = 1
	if a[i] < min:
		min = a[i]
		mini = i
for i in range(k, n):
	if a[i] > min:
		max.pop(mini)
		if mini == k - 1:
			dist[mini - 1] += dist[mini]
		else:
			dist[mini + 1] += dist[mini]
		dist.pop(mini)
		max.append(a[i])
		dist.append(1)
		min = 2001
		for j in range(k):
			if max[j] < min:
				min = max[j]
				mini = j
	else:
		dist[k - 1] += 1
print(sum(max))
if k == 1:
	print(n)
else:
	for i in range(k):
		print(dist[i], '', end='')


(n, k) = map(int, input().split())
(profits, last_problems) = zip(*sorted(((x, i) for (i, x) in enumerate(map(int, input().split()))))[-k:])
print(sum(profits))
last_problems = sorted(last_problems)
if k == 1:
	print(n)
else:
	print(last_problems[0] + 1, end=' ')
	for i in range(1, len(last_problems) - 1):
		print(last_problems[i] - last_problems[i - 1], end=' ')
	print(n - last_problems[-2] - 1)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(list(enumerate(a)), key=lambda x: x[1], reverse=True)
amax = sorted(a[:k])
sumamax = 0
for (i, ai) in amax:
	sumamax += ai
print(sumamax)
if k > 1:
	print(amax[0][0] + 1, end=' ')
	for i in range(1, k - 1):
		print(amax[i][0] - amax[i - 1][0], end=' ')
	print(n - amax[-2][0] - 1)
else:
	print(n)


(z, x) = map(int, input().split())
c = list(map(int, input().split()))
a = ['0'] * z
for i in range(z):
	a[i] = [c[i], i]
a.sort(reverse=True)
s = []
q = 0
for i in range(x):
	s.append(a[i][1] + 1)
	q += a[i][0]
print(q)
s.sort()
w = []
if len(s) == 1:
	print(z)
else:
	r = []
	e = 0
	for i in range(len(s)):
		if i + 1 == len(s):
			r.append(len(c) - e)
		elif i == 0:
			r.append(s[i] - e)
			e = s[i]
		else:
			r.append(s[i] - e)
			e = s[i]
	print(*r)


(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
indexedNums = [(nums[i], i) for i in range(len(nums))]
indexedNums.sort()
indexedNums.reverse()
indexedNums = indexedNums[:k]
indices = [indexedNums[i][1] for i in range(len(indexedNums))]
sum = 0
for i in range(len(indices)):
	sum = sum + nums[indices[i]]
indices.sort()
indices.pop()
indices.append(-1)
indices.append(n - 1)
indices.sort()
gaps = [indices[i + 1] - indices[i] for i in range(len(indices) - 1)]
print(sum)
print(*gaps)


import sys
import io
stream_enable = 0
inpstream = '\n\n'
if stream_enable:
	sys.stdin = io.StringIO(inpstream)
	input()

def inpmap():
	return list(map(int, input().split()))
(n, k) = inpmap()
arr = inpmap()
ar = arr[:]
ar.sort()
b = ar[-k:]
print(sum(b))
m = 0
r = []
for (i, x) in enumerate(arr):
	if x in b:
		b.remove(x)
		r.append(i - m + 1)
		m = i + 1
r[-1] += n - m
print(*r)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(sorted(a))
lista = []
soma = 0
for i in range(n - 1, n - k - 1, -1):
	soma += b[i]
	x = a.index(b[i])
	lista.append(x)
	a[x] = -1
lista.sort()
print(soma)
lista = [-1] + lista
for i in range(1, len(lista) - 1):
	print(lista[i] - lista[i - 1], end=' ')
print(n - lista[-2] - 1)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = sorted(a)
	topk = b[-k:]
	topk.sort(reverse=True)
	positions = [-1]
	used = [False] * n
	for val in topk:
		for i in range(n):
			if a[i] == val and (not used[i]):
				positions.append(i)
				used[i] = True
				break
	positions.sort()
	res = []
	for i in range(1, k):
		res.append(positions[i] - positions[i - 1])
	res.append(positions[k] - positions[k - 1] + n - 1 - positions[k])
	print(sum(topk))
	print(*res)
main()


(n, k) = map(int, input().split())
L = [[int(c), i] for (i, c) in enumerate(input().split())]
L.sort()
ans = 0
ind = [0] * (k + 1)
ind[k] = n
j = 0
for i in range(n - k, n):
	ans += L[i][0]
	ind[j] = L[i][1]
	j += 1
ind.sort()
ind[0] = 0
print(ans)
for i in range(1, k + 1):
	print(ind[i] - ind[i - 1], end=' ')


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = sorted(a, reverse=True)
b = b[:k]
c = [0] * 3000
maxprofit = sum(b)
for e in b:
	c[e] += 1
part = 1
tc = 1
print(maxprofit)
for i in range(len(a)):
	if c[a[i]]:
		c[a[i]] -= 1
		if tc == k:
			print(n - i + part - 1)
		else:
			print(part, end=' ')
		part = 0
		tc += 1
	part += 1


(n, k) = map(int, input().split())
a = [*map(int, input().split())]
m = dict()
for i in range(n):
	m[i] = a[i]
r = dict(sorted(m.items(), key=lambda x: x[1])[-k:])
print(sum(r.values()))
keys = sorted(r.keys())
d = [keys[0] + 1]
for i in range(1, k):
	d.append(keys[i] - keys[i - 1])
d[k - 1] += n - 1 - keys[k - 1]
print(*d, sep=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
rs = 0
p = list()
for i in range(k):
	rs += b[i]
	p.append(b[i])
print(rs)
dem = 0
for i in a:
	dem += 1
	if i in p and len(p) > 1:
		p.remove(i)
		print(dem, end=' ')
		dem = 0
print(dem)


(n, k) = map(int, input().split())
l = [int(i) for i in input().split()]
if k == 1:
	print(max(l))
	print(n)
	exit()
l = [[l[i], i] for i in range(n)]
l.sort(reverse=1)
print(sum((l[i][0] for i in range(k))))
ind = [l[i][1] for i in range(k)]
ind.sort()
prev = -1
ans = []
for i in ind:
	ans.append(i - prev)
	prev = i
ans.pop()
sm = sum(ans)
ans.append(n - sm)
print(*ans)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
if k == 1:
	print(max(a))
	print(n)
	exit()
for i in range(n):
	a[i] = [a[i], i]
a.sort()
o = []
s = 0
for u in range(k):
	s += a[n - u - 1][0]
	o.append(a[n - u - 1][1] + 1)
print(s)
o.sort()
bal = 0
cnt = 0
for i in range(1, n + 1):
	bal += 1
	if i == o[cnt]:
		print(bal, end=' ')
		bal = 0
		cnt += 1
		if cnt == k - 1:
			o[cnt] = n


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = a[:]
b.sort()
r = b[n - k:]
d = dict()
for i in range(n):
	try:
		d[a[i]]
	except:
		d[a[i]] = [i]
	else:
		d[a[i]].append(i)
print(sum(r))
for i in range(k - 1, -1, -1):
	r[i] = d[r[i]].pop()
r.sort()
r[0] = 0
r.append(n)
ind = [0] * k
for i in range(0, k):
	ind[i] = r[i + 1] - r[i]
for i in range(k):
	print(ind[i], end=' ')


def func():
	Max = 0
	ID = -1
	for i in range(n):
		if Max <= x[i] and (not check[i]):
			Max = x[i]
			ID = i
	check[ID] = True
	return Max
(n, k) = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
check = [False] * n
ans = 0
for _ in range(k):
	ans += func()
print(ans)
tmp = 0
for i in range(n):
	tmp += 1
	if k == 1:
		print(n - i)
		break
	if check[i]:
		print(tmp, end=' ')
		k -= 1
		tmp = 0


r = lambda : int(input())
ra = lambda : [*map(int, input().split())]
p = lambda a: print('{:.6f}'.format(a))
(n, k) = ra()
a = ra()
b = sorted(a)
m = []
a = a[::-1]
an = [[] for i in range(k)]
for i in range(k):
	m.append(b.pop())
print(sum(m))
for i in range(k):
	while True:
		an[i].append(a.pop())
		if an[i][len(an[i]) - 1] in m:
			m.remove(an[i][len(an[i]) - 1])
			break
an[i] = an[i] + a
for i in range(k):
	print(len(an[i]), end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)[:k]
prev = 0
print(sum(b))
res = []
for (ind, elem) in enumerate(a):
	if len(b) == 1:
		res.append(n - ind)
		break
	if elem in b:
		res.append(ind + 1 - prev)
		prev = ind + 1
		b.remove(elem)
print(*res)


(N, K) = map(int, input().split())
a = list(input().split(' '))
b = []
id = 0
for id in range(0, N):
	b.append((int(a[id]), id))
b = sorted(b)
c = []
ans = 0
for id in range(N - K, N):
	ans = ans + b[id][0]
	c.append(b[id][1])
c = sorted(c)
print(ans)
if K != 1:
	print(c[0] + 1, end=' ')
for id in range(1, K - 1):
	print(c[id] - c[id - 1], end=' ')
if K != 1:
	print(N - 1 - c[K - 2])
else:
	print(N)


from sys import stdin, stdout

def main():
	(n, k) = map(int, stdin.readline().strip().split())
	A = list(map(int, stdin.readline().strip().split()))
	req = sorted(A)[-1 * k:]
	index = {}
	for (j, i) in enumerate(A):
		if index.get(i, -1) == -1:
			index[i] = [j]
		else:
			index[i].append(j)
	b = {}
	t = []
	outputs = []
	for i in req:
		t.append(index.get(i)[b.get(i, 0)])
		b[i] = b.get(i, 0) + 1
	t.sort()
	if k == 1:
		outputs.append(str(n))
	else:
		for (i, j) in enumerate(t):
			if i == 0:
				outputs.append(str(j + t[i + 1] - j))
			elif i == k - 1:
				outputs.append(str(n - j))
			else:
				outputs.append(str(t[i + 1] - j))
	print(sum(req))
	print(' '.join(outputs))
main()


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
dic = {}
for (idx, arr) in enumerate(arr):
	dic[idx] = arr
cnt = 0
ans = 0
ans_dic = {}
dic = dict(sorted(dic.items(), key=lambda x: x[-1], reverse=True))
for (key, value) in dic.items():
	ans = ans + value
	cnt = cnt + 1
	ans_dic[key] = value
	if cnt >= k:
		break
print(ans)
cnt = 0
pre = 0
ans_dic = dict(sorted(ans_dic.items(), key=lambda x: x[0], reverse=False))
for (key, value) in ans_dic.items():
	if cnt == 0:
		pass
	elif cnt == 1:
		print(key, end='')
	else:
		print(' ', end='')
		print(key - pre, end='')
	cnt = cnt + 1
	pre = key
	if cnt >= k:
		break
if k != 1:
	print(' ', end='')
	print(len(dic) - pre)
else:
	print(len(dic))


from copy import *
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = copy(arr)
arr.sort()
arr2 = []
print(sum(arr[n - k:]))
for i in range(k):
	z = arr1.index(arr[n - 1 - i])
	arr1[z] = 0
	arr2.append(z + 1)
arr2.sort()
arr2[-1] = n
arr3 = []
arr3.append(arr2[0])
for i in range(1, len(arr2)):
	arr3.append(arr2[i] - arr2[i - 1])
print(*arr3)


import sys
sys.setrecursionlimit(10 ** 4)
[N, K] = [int(c) for c in input().split()]
arr = [int(c) for c in input().split()]
arr2 = sorted(arr[:])
nums = []
out1 = 0
out2 = []
for c in range(N - 1, N - 1 - K, -1):
	nums.append(arr2[c])
out1 = sum(nums)
prev = -1
for c in range(N):
	if len(out2) == K - 1:
		out2.append(str(N - c))
		break
	if arr[c] in nums:
		out2.append(str(c - prev))
		nums.pop(nums.index(arr[c]))
		prev = c
print(out1)
print(' '.join(out2))


(n, k) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr1 = sorted(arr, reverse=True)
new = arr1[:k]
suma = 0
newarr = arr
idxs = []
res = []
if k == 1:
	print(arr1[0])
	print(n)
	exit()
for i in range(k):
	suma += new[i]
	idxs.append(arr.index(new[i]))
	arr[idxs[i]] = -100
idxs = sorted(idxs)
for i in range(k - 1):
	if i == 0:
		res.append(idxs[1])
		continue
	res.append(idxs[i + 1] - idxs[i])
res.append(n - idxs[-1])
print(suma)
print(*res)


l = list(map(int, input().split()))
s = list(map(int, input().split()))
n = int(l[0])
k = int(l[1])
b = s.copy()
b.sort()
a = b[n - k:n]
cl = []
count = 0
sum1 = sum(a)
z = 1
setlen = len(set(a))
cl = []
sum2 = 0
req = k
print(sum1)
for i in range(n):
	count = count + 1
	if s[i] in a:
		if req == 1:
			cl.append(n - sum2)
			print(n - sum2)
			break
		else:
			cl.append(count)
			print(count, end=' ')
			sum2 = sum2 + count
			a.remove(s[i])
			req = req - 1
			count = 0


(n, k) = map(int, input().split())
lis = list(map(int, input().split()))
if k == 1:
	print(max(lis))
	print(n)
	exit()
li = [[lis[i], i] for i in range(n)]
li.sort(reverse=True)
li = li[:k]
li = [[li[i][1], li[i][0]] for i in range(k)]
li.sort()
prev = 0
ans = []
ans.append(li[0][0] + 1)
prev = li[0][0]
for i in range(1, k - 1):
	ans.append(li[i][0] - prev)
	prev = li[i][0]
if n - prev - 1 != 0:
	ans.append(n - prev - 1)
an = sum(sorted(lis, reverse=True)[:k])
print(an)
print(*ans)


(n, k) = map(int, input().split())
data = list(map(int, input().split()))
an_data = [(data[i], i) for i in range(n)]
an_data.sort(key=lambda x: x[0])
an_data = an_data[::-1]
ans = 0
answer = []
for i in range(k):
	ans += an_data[i][0]
	answer.append(an_data[i][1])
print(ans)
prev = 0
answer.sort()
for i in range(k):
	el = answer[i]
	if i == k - 1:
		print(n - prev)
		break
	if prev == 0:
		print(el + 1, end=' ')
		prev = el + 1
		continue
	print(el - prev + 1, end=' ')
	prev = el + 1


(n, k) = [int(x) for x in input().split(' ')]
z = [int(x) for x in input().split(' ')]
zz = z[::-1]
zz.sort()
zz.reverse()
ind = []
c = 0
s = 0
for x in zz:
	c += 1
	ind.append(z.index(x))
	z[z.index(x)] = -1
	s += x
	if c == k:
		break
ind.sort()
print(s)
if k == 1:
	print(n)
else:
	for i in range(k):
		if i == 0:
			print(ind[i] + 1, end=' ')
		elif i != k - 1:
			print(ind[i] - ind[i - 1], end=' ')
		else:
			print(n - 1 - ind[k - 2])


(k, d) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(k):
	b.append([a[i], i + 1])
b = sorted(b)[k - d:]
c = sorted([i[1] for i in b])
e = 0
for i in b:
	e += i[0]
print(e)
if d == 1:
	print(k)
else:
	print(c[0], end=' ')
	for i in range(d - 2):
		print(c[i + 1] - c[i], end=' ')
	print(k - c[-2])


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
temp = sorted(a, reverse=True)
g = []
for i in range(k):
	g.append(temp[i])
print(sum(g))
curr = 0
i = 0
while i < len(a):
	curr += 1
	if a[i] in g:
		g.remove(a[i])
		if len(g) == 0:
			print(curr + len(a) - i - 1)
		else:
			print(curr, end=' ')
		curr = 0
	i += 1


(n, k) = map(int, input().split())
a = [[x, i] for (i, x) in enumerate(map(int, input().split()))]
a.sort(reverse=True)
score = 0
start = -1
order = []
for i in range(k):
	score += a[i][0]
	order.append(a[i][1])
order.sort()
ans_order = []
for x in order[:-1]:
	ans_order.append(str(x - start))
	start = x
ans_order.append(str(n - start - 1))
print(score)
print(' '.join(ans_order))


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def test():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = []
	for i in range(n):
		d.append([l[i], i + 1])
	d.sort(reverse=True)
	m = []
	s = 0
	for i in range(k):
		m.append(d[i][1])
		s += d[i][0]
	print(s)
	m.sort()
	if k == 1:
		print(n)
	else:
		ans = [m[0]]
		for i in range(1, k - 1):
			ans.append(m[i] - m[i - 1])
		ans.append(n - m[k - 2])
		print(*ans)
t = 1
while t:
	test()
	t -= 1


def main():
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	f = l.__getitem__
	idx = sorted(sorted(range(n), key=f)[-m:])
	print(sum(map(f, idx)))
	idx[0] = 0
	print(*[b - a for (a, b) in zip(idx, idx[1:] + [n])])
main()


(n, k) = map(int, input().split())
problems = list(map(int, input().split()))
s_problems = sorted(problems)
total = 0
largest = []
for i in range(len(problems) - 1, len(problems) - 1 - k, -1):
	total += s_problems[i]
	largest.append(s_problems[i])
count = 1
answer = []
for e in problems:
	if len(largest) > 1 and e in largest:
		largest.remove(e)
		answer.append(str(count))
		count = 0
	count += 1
answer.append(str(count - 1))
print(total)
print(' '.join(answer))


def mergeSort(A):
	if len(A) <= 1:
		return A
	else:
		L = A[:len(A) // 2]
		R = A[len(A) // 2:]
		return merge(mergeSort(L), mergeSort(R))

def merge(A, B):
	i = 0
	j = 0
	Res = []
	while i < len(A) and j < len(B):
		if A[i][1] <= B[j][1]:
			Res.append(A[i])
			i += 1
		else:
			Res.append(B[j])
			j += 1
	Res += A[i:] + B[j:]
	return Res
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
M = [0] * k
used = [False] * n
ans = 0
for i in range(k):
	m = -1
	ind = -1
	for j in range(n):
		if A[j] > m and (not used[j]):
			m = A[j]
			ind = j
	M[i] = [m, ind]
	used[ind] = True
	ans += m
M = [[0, -1] for i in range(1)] + mergeSort(M)
print(ans)
for i in range(1, k):
	print(M[i][1] - M[i - 1][1], end=' ')
print(n - M[k - 1][1] - 1)


def main():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr2 = []
	arr3 = []
	if k == 1:
		print(max(arr))
		print(n)
		return
	for i in range(n):
		arr3.append([arr[i], i])
	arr3.sort(reverse=True)
	add = 0
	for i in range(k):
		arr2.append(arr3[i][1])
		add += arr3[i][0]
	arr2.sort()
	print(add)
	for i in range(k - 1):
		if i == 0:
			print(arr2[i] + 1, end=' ')
		else:
			print(arr2[i] - arr2[i - 1], end=' ')
	if len(arr2) - 2 >= 0:
		print(n - 1 - arr2[k - 2], end=' ')
	return
main()


(n, k) = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
a1 = sorted(a)
a1 = a1[n - k:]
max = 0
for i in a1:
	max += i
print(max)
count = 0
mas = []
k1 = 0
for i in range(n):
	if a[i] in a1:
		a1.remove(a[i])
		k1 += 1
		count += 1
		if k1 == k:
			count = count + n - i - 1
			mas.append(count)
			break
		else:
			mas.append(count)
			count = 0
	else:
		count += 1
for i in mas:
	print(i, end=' ')


from functools import reduce
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
sort = sorted(l)
vals = sort[-k:]
sum = 0
indices = []
for i in range(n):
	if l[i] in vals:
		sum += l[i]
		vals.remove(l[i])
		indices.append(i)
print(sum)
indices.append(n)
indices[0] = 0
sizes = []
for i in range(k):
	sizes.append(indices[i + 1] - indices[i])
s = reduce(lambda x, y: str(x) + ' ' + str(y), sizes)
print(s)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = arr[:]
arr1.sort(reverse=True)
ans = 0
flag = 0
list1 = []
if k == 1:
	print(max(arr))
	print(n)
else:
	for i in range(k):
		temp = arr1[i]
		ans += arr1[i]
		flag = 0
		for j in range(n):
			if arr[j] == temp:
				if j in list1:
					continue
				else:
					list1.append(j)
					break
	list1.sort()
	arrfinal = []
	arrfinal.append(list1[0] + 1)
	for i in range(1, k - 1):
		arrfinal.append(list1[i] - list1[i - 1])
	arrfinal.append(n - list1[k - 2] - 1)
	print(ans)
	for i in arrfinal:
		print(i, end=' ')


__author__ = 'liuzixiang'

def main():
	(n, k) = list(map(int, input().split()))
	v = list(map(int, input().split()))
	v_sort = v.copy()
	v_sort.sort(reverse=True)
	mx = v_sort[0]
	count = [0 for i in range(mx + 1)]
	for i in range(k):
		count[v_sort[i]] += 1
	ans = 0
	pre = 0
	result = []
	for x in v:
		pre += 1
		if count[x] == 0:
			continue
		count[x] -= 1
		ans += x
		if len(result) + 1 < k:
			result.append(pre)
			pre = 0
	result.append(pre)
	print(ans)
	for x in result:
		print(x, end=' ')
main()


(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
a_sorted = sorted(range(n), key=lambda x: a[x], reverse=True)
ind = sorted(a_sorted[:k])
t = -1
ans = []
total = 0
for i in range(k):
	total += a[ind[i]]
	if i == k - 1:
		ans.append(n - t - 1)
	else:
		ans.append(ind[i] - t)
	t = ind[i]
print(total)
print(' '.join([str(x) for x in ans]))


def check(d):
	if len(d) == 1:
		flag = 0
		for i in d.keys():
			if d[i] == 1:
				return True
	return False
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = sorted(arr[:], reverse=True)
print(sum(arr1[:k]))
d = {}
for i in arr1[:k]:
	if i in d.keys():
		d[i] += 1
	else:
		d[i] = 1
ans = []
for i in range(n):
	if check(d):
		ans.append(n)
		break
	if arr[i] in d.keys():
		d[arr[i]] -= 1
		if d[arr[i]] == 0:
			del d[arr[i]]
		ans.append(i + 1)
print(ans[0], end=' ')
for i in range(1, len(ans)):
	print(ans[i] - ans[i - 1], end=' ')
print('')


(n, k) = map(int, input().split())
s = list(map(int, input().split()))
sl = s[:]
sl.sort()
sl.reverse()
p = sl[0:k]
m = sum(p)
vall = [0 for i in range(2005)]
for i in p:
	vall[i] += 1
sl = []
t = 0
for i in range(n):
	if vall[s[i]] >= 1:
		sl += [i + 1]
		vall[s[i]] -= 1
summ = 0
for i in range(0, k):
	sl[i] = sl[i] - summ
	summ += sl[i]
if sum(sl) < n:
	sl[k - 1] += n - sum(sl)
print(m)
sll = ''
for i in sl:
	sll += str(i) + ' '
print(sll)


(n, k) = map(int, input().split())
s = [int(elem) for elem in input().split()]
anses = []
s2 = s[:]
s2.sort(reverse=True)
s2 = s2[:k]
ans = sum(s2)
arr = []
e = 0
for i in range(n):
	if s[i] in s2:
		anses.append(str(i - e + 1))
		e = i + 1
		b = s2.index(s[i])
		del s2[b]
if e - 1 < n:
	anses[len(anses) - 1] = str(int(anses[len(anses) - 1]) + n - e)
print(ans)
print(' '.join(anses))


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = []
for i in range(n):
	arr1.append(arr[i])
arr1.sort()
arr1 = arr1[n - k:]
print(sum(arr1))
prev = 0
ans = list()
for i in range(0, n):
	if arr[i] in arr1:
		k -= 1
		if k == 0:
			ans.append(n - prev)
		else:
			ans.append(i - prev + 1)
		prev = i + 1
		arr1.remove(arr[i])
print(*ans)


(n, k) = map(int, input().split())
a = input().split()
ls = []
for i in range(n):
	ls.append([int(a[i]), i])
ls.sort(reverse=True)
ans = 0
indices = []
for i in range(k):
	ans += ls[i][0]
	indices.append(ls[i][1])
indices.sort()
print(ans)
if k == 1:
	print(n)
else:
	for i in range(k):
		if i == 0:
			print(indices[i] + 1, end=' ')
		elif i == k - 1:
			print(n - 1 - indices[i - 1], end=' ')
		else:
			print(indices[i] - indices[i - 1], end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
b = b[n - k:]
m = max(b)
v = [0] * (m + 1)
print(sum(b))
for i in b:
	v[i] += 1
cnt = 1
res = []
for i in range(n):
	if sum(v) == 1:
		res.append(n - sum(res))
		break
	if v[a[i]] > 0:
		res.append(cnt)
		cnt = 1
		v[a[i]] -= 1
	else:
		cnt += 1
print(*res)


(n, k) = map(int, input().split())
a = []
s = input().split()
for i in range(len(s)):
	a.append([int(s[i]), i])
b = sorted(a)
c = b[n - k:]
sum = 0
for i in range(len(c)):
	sum += c[i][0]
print(sum)
c.sort(key=lambda x: x[1])
kr = -1
c[-1][1] = n - 1
for i in range(k):
	print(c[i][1] - kr, end=' ')
	kr = c[i][1]


(n, k) = map(int, input().split())
z = list(map(int, input().split()))
a = [(z[i], i) for i in range(len(z))]
z.sort()
pol = sum(z[-k:])
print(pol)
a.sort()
zmax = a[-k:]
zmaxind = [int(zmax[i][1]) for i in range(-k, 0)]
zmaxind.sort()
zmaxind.pop()
zmaxind.append(len(z) - 1)
zmaxind.append(-1)
zmaxind.sort()
for i in range(len(zmaxind) - 1):
	print(zmaxind[i + 1] - zmaxind[i], end=' ')


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = a[:]
a.sort()
tmp = a[-m]
cnt = 1
ans = tmp
for i in range(n - m + 1, len(a)):
	ans += a[i]
	if a[i] == tmp:
		cnt += 1
c = []
count = 0
for i in range(len(b)):
	count += 1
	if b[i] > tmp:
		c.append(count)
		count = 0
	elif b[i] == tmp:
		if cnt > 0:
			c.append(count)
			count = 0
			cnt -= 1
c[-1] += count
print(ans)
for x in c:
	print(x, end=' ')


(N, K) = map(int, input().split(' '))
DIFFS = list(map(lambda x: int(x.strip()), input().split()))
MAXS = sorted(DIFFS)[-K:]
print(sum(MAXS))
FIRST_DAY = True
PER_DAY = [0]
for d in DIFFS:
	if d in MAXS:
		if FIRST_DAY:
			PER_DAY.append(PER_DAY.pop() + 1)
			FIRST_DAY = False
		else:
			PER_DAY.append(1)
		MAXS.remove(d)
	else:
		PER_DAY.append(PER_DAY.pop() + 1)
print(' '.join(map(str, PER_DAY)).strip())


(z, R) = (input, lambda : map(int, z().split()))
(n, k) = R()
a = sorted(zip(R(), range(n)))[-k:]
print(sum((x[0] for x in a)))
b = sorted((x[1] for x in a)) + [n]
b[0] = 0
print(*(y - x for (x, y) in zip(b, b[1:])))


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = sorted(a)
b = b[::-1]
b = b[:k]
s = sum(b)
ind = []
c = 0
for i in range(n):
	if a[i] in b:
		c += 1
		ind.append(c)
		c = 0
		b.remove(a[i])
	else:
		c += 1
print(s)
for i in ind[:-1]:
	print(i, end=' ')
print(ind[-1] + c)


(noe, k) = [int(x) for x in input().split()]
problems = [(int(x), i) for (i, x) in enumerate(input().split())]
probss = sorted(problems, key=lambda x: x[0], reverse=True)[:k]
print(sum((x[0] for x in probss)))
indxs = sorted((i for (v, i) in probss))
indxs[-1] = noe - 1
print(*[y - x for (x, y) in zip([-1] + indxs, indxs)])


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
if k == 1:
	print(max(l))
	print(n)
else:
	lm = []
	sum = 0
	for i in range(k):
		sum += max(l)
		a = l.index(max(l))
		lm += [a]
		l[a] = -1
	lm.sort()
	for i in range(k):
		if i == k - 1:
			print(n - 1 - lm[k - 2], end=' ')
		elif i == 0:
			print(sum)
			print(lm[0] + 1, end=' ')
		else:
			print(lm[i] - lm[i - 1], end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list()
for i in range(n):
	b.append(a[i])
a.sort(reverse=True)
sn = 0
for i in range(k):
	sn += a[i]
c = list()
for i in range(k):
	for j in range(n):
		if a[i] == b[j]:
			b[j] = -1
			c.append(j)
			break
c.sort()
d = list()
if len(c) >= 2:
	d.append(c[1])
for i in range(2, len(c)):
	d.append(c[i] - c[i - 1])
if k != 1:
	d.append(n - c[-1])
else:
	d.append(n)
print(sn)
print(*d)


(n, k) = map(int, input().split())
a = sorted(list(map(lambda x: (x[1], x[0]), enumerate(map(int, input().split())))), reverse=True)
print(sum(map(lambda x: x[0], a[:k])))
p = -1
r = []
for i in sorted(map(lambda x: x[1], a[:k])):
	r.append(i - p)
	p = i
r[-1] += n - i - 1
print(*r)


(np, d) = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
o = []
for i in p:
	o += [i]
o.sort()
jc = -1
soma = 0
m = []
for i in range(d):
	m += [o[jc]]
	soma += o[jc]
	jc -= 1
txt = ''
i = 0
j = 0
enc = 0
while i < np:
	if len(m) == 1:
		if txt == '':
			txt += str(np - i)
		else:
			txt += ' ' + str(np - i)
		break
	if p[i] in m:
		if txt == '':
			txt += str(i - j + 1)
		else:
			txt += ' ' + str(i - j + 1)
		m.remove(p[i])
		j = i + 1
	i += 1
print(soma)
print(txt)


isVerbose = False

def v(msg):
	if isVerbose:
		print(msg)
(n, k) = map(int, input().split())
nums = list(enumerate(map(int, input().split())))
nums.sort(key=lambda tup: tup[1])
nums_top = nums[-min(k, n):]
nums_top.sort(key=lambda tup: tup[0])
print(sum([pair[1] for pair in nums_top]))
last = -1
for i in range(len(nums_top) - 1):
	print(nums_top[i][0] - last, end=' ')
	last = nums_top[i][0]
print(n - 1 - last)


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

def find_k_best(k, n, diff):
	k_best_value = [0] * k
	k_best_index = [0] * k
	for i in range(n):
		j = 0
		while j < k:
			if diff[i] >= k_best_value[j]:
				k_best_value = k_best_value[:j] + [diff[i]] + k_best_value[j:-1]
				k_best_index = k_best_index[:j] + [i] + k_best_index[j:-1]
				j = k
			j += 1
	return (k_best_value, k_best_index)
(v, i) = find_k_best(k, n, diff)
s = sum(v)
i.sort()
i[-1] = n - 1
idx = [i[0] + 1]
for t in range(1, len(i)):
	idx.append(i[t] - i[t - 1])
print(sum(v))
str_idx = ''
for t in range(len(idx)):
	str_idx += str(idx[t]) + ' '
print(str_idx[:-1])


(n, k) = map(int, input().split())
l = [int(x) for x in input().split()]
p = sorted(l)
p = p[n - k:]
if k == 1:
	print(max(l))
	print(n)
else:
	d = {}
	for i in p:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ans1 = []
	ans2 = []
	i = 0
	c = 0
	while i < len(l):
		if l[i] in d and d[l[i]] > 0:
			d[l[i]] -= 1
			c += 1
			ans1.append(l[i])
			ans2.append(c)
			c = 0
		else:
			c += 1
		if len(ans2) == k - 1:
			ans1.append(max(l[i + 1:]))
			ans2.append(n - sum(ans2))
			break
		i += 1
	print(sum(ans1))
	print(' '.join([str(i) for i in ans2]))


I = lambda : map(int, input().split())
INT = lambda : int(input())
T = 1
for _ in range(T):
	(n, k) = I()
	a = list(I())
	a = sorted([(a[i], i) for i in range(n)], reverse=True)[:k]
	print(sum([v for (v, i) in a]))
	a = sorted([i for (v, i) in a])
	a[-1] = n - 1
	print(' '.join((str(y - x) for (x, y) in zip([-1] + a, a))))


(length, k) = map(int, input().split())
problems = list(enumerate(map(int, input().split(' '))))
problems.sort(key=lambda i: i[1], reverse=True)
maxs = problems[:k]
maxs.sort()
distr = []
prev = -1
total = 0
for i in range(k):
	distr.append(maxs[i][0] - prev)
	prev = maxs[i][0]
	total += distr[-1]
distr[-1] += length - total
print(sum(map(lambda i: i[1], maxs)))
print(*distr)


f = lambda : map(int, input().split())
(n, k) = f()
a = list(f())
b = [(i, a[i]) for i in range(n)]
b.sort(key=lambda x: x[1], reverse=True)
index = [-1]
s = 0
for i in range(k):
	s += b[i][1]
	index.append(b[i][0])
index.sort()
index.pop()
index.append(n - 1)
print(s)
for i in range(k):
	print(index[i + 1] - index[i], end=' ')


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
bs = [[x, i + 1] for (i, x) in enumerate(arr)]
bs.sort(reverse=True)
cs = [bs[i][1] for i in range(k)]
ans = sum((bs[i][0] for i in range(k)))
cs.sort()
print(ans)
if k == 1:
	print(n)
else:
	print(cs[0], end=' ')
	for i in range(1, k - 1):
		print(cs[i] - cs[i - 1], end=' ')
	print(n - cs[k - 2])


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
s = sorted(zip(arr, list(range(n))), reverse=True)
s = s[:k]
print(sum((x for (x, _) in s)))
s.sort(key=lambda x: x[1])
prev = -1
ans = []
for (x, i) in s[:-1]:
	n -= i - prev
	ans.append(i - prev)
	prev = i
ans.append(n)
print(*ans)


(z, zz) = (input, lambda : list(map(int, z().split())))
zzz = lambda : [int(i) for i in stdin.readline().split()]
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from string import *
from re import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from itertools import accumulate as ac
from itertools import permutations as permu

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2 or x == 0:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = True
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)
num = 1
for _ in range(num):
	(n, k) = zz()
	arr = zzz()
	lst = []
	ans = sorted(arr)[n - k:]
	j = 1
	kp = 0
	t = 1
	if k == 1:
		print(max(arr))
		print(n)
		continue
	print(sum(ans))
	for i in arr:
		if i in ans:
			ans.remove(i)
			print(j - kp, end=' ')
			kp = j
			t += 1
		if t >= k:
			break
		j += 1
	print(n - j)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = a.copy()
b.sort()
arr = b[-k:]
last = -1
summ = sum(arr)
days = list()
for i in range(n):
	if a[i] in arr:
		arr.remove(a[i])
		days.append(i - last)
		last = i
		if len(arr) == 0:
			days[-1] += n - i - 1
print(summ)
print(*days)


(n, k) = input().split()
n = int(n)
k = int(k)
m = list(map(int, input().split()))
x = m[:]
x.sort(reverse=True)
a = []
for i in range(0, k):
	a.append(x[i])
j = 0
b = []
an = 0
for i in m:
	j += 1
	if i in a:
		an += i
		a.remove(i)
		if len(a) != 0:
			b.append(j)
			j = 0
b.append(j)
print(an)
print(*b)


(n, t) = input().split(' ')
(n, t) = (int(n), int(t))
T = input().split(' ')
for i in range(n):
	T[i] = (int(T[i]), i + 1)
T.sort()
c = 0
J = []
for i in range(t):
	c = c + T[n - 1 - i][0]
	J.append(T[n - 1 - i][1])
J.sort()
print(c)
j = 0
for i in range(t - 1):
	print(J[i] - j, end=' ')
	j = J[i]
print(n - j)


import sys
(n, k) = map(int, sys.stdin.readline().split())
array = map(int, sys.stdin.readline().split()[:n])
pair = sorted(((e, i) for (i, e) in enumerate(array)))[n - k:]
pair = sorted(pair, key=lambda x: x[1])
max = 0
list = list()
pos = 0
for point in pair:
	max += point[0]
for (i, point) in enumerate(pair):
	if i < len(pair) - 1:
		list.append(point[1] - pos + 1)
		pos = point[1] + 1
	else:
		list.append(n - pos)
print(max)
print(*list)


aaaa = [0] * 2000
aaa = [0] * 2000
aq = 0
aqq = 0
w = 0
q = input()
q = q.split()
n = int(q[0])
m = int(q[1])
a = input()
a = a.split()
aa = a.copy()
for i in range(len(a)):
	a[i] = int(a[i])
	aa[i] = a[i]
aa = sorted(a, reverse=True)
for i in range(n):
	w += 1
	if aa.index(a[i]) < m:
		aa[aa.index(a[i])] = -1
		aaa[aq] = w
		aq += 1
		aqq += a[i]
		w = 0
aaa[aq - 1] += w
print(aqq)
for i in range(aq):
	print(aaa[i], end=' ')


(n, k) = map(int, input().split(' '))
numbers = [int(i) for i in input().split(' ')]
numbers = [(num, i + 1) for (i, num) in enumerate(numbers)]
numbers = sorted(numbers)
numbers = numbers[::-1][:k]
indices = [i[1] for i in numbers]
indices = sorted(indices)
for i in range(k - 1, 0, -1):
	indices[i] -= indices[i - 1]
s = sum(indices)
indices[-1] += n - s
print(sum([i[0] for i in numbers]))
print(*indices)


import re
a = input().split(' ')
b = list(map(int, input().split(' ')))
max_profit = sorted(b)[-int(a[1]):]
print(sum(max_profit))
order = ''
for elem in b:
	if elem in max_profit:
		order += '1'
		max_profit.remove(elem)
	else:
		order += '0'
for item in re.findall('0*10*', order):
	print(len(item), end=' ')


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
greedyBois = sorted(a)[::-1][:k]
print(sum(greedyBois))
ans = []
i = 1
m = n
for x in range(n):
	if a[x] in greedyBois:
		if len(greedyBois) != 1:
			ans.append(i)
		else:
			ans.append(m)
		m -= i
		i = 1
		greedyBois.remove(a[x])
	else:
		i += 1
print(*ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * 3000
for i in range(n):
	a[i] = (i, a[i])
a.sort(key=lambda x: x[1], reverse=True)
for i in range(k):
	b[a[i][0]] = 1
cur = 0
ans = []
total = 0
addtolast = 0
a.sort(key=lambda x: x[0])
for i in range(n):
	if b[i] == 1:
		total += a[i][1]
		ans.append(i - cur + 1)
		addtolast = n - i - 1
		cur = i + 1
ans[-1] += addtolast
print(total)
print(*ans)


(n, k) = map(int, input().split())
a = [int(s) for s in input().split()]
m = [0] * k
ind = []
ar = sorted(a)
ar = ar[n - k:]
for i in range(n):
	if a[i] in ar and i not in ind:
		ind.append(i)
		ar.remove(a[i])
ind = sorted(ind)
ind.insert(k, n)
pol = 0
ar = sorted(a)
ar = ar[n - k:]
for i in range(k):
	pol += ar[i]
dif = [str(ind[i] - ind[i - 1]) for i in range(2, k + 1)]
dif.insert(0, str(ind[1]))
print(pol)
print(' '.join(dif))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a2 = []
for i in range(n):
	a2.append((i, a[i]))
a_max = sorted(a2, key=lambda x: x[1])[n - k:]
a_max.sort(key=lambda x: x[0])
summa = 0
for ai in a_max:
	summa += ai[1]
print(summa)
if k > 2:
	print(a_max[0][0] + 1, end=' ')
	for i in range(1, k - 1, 1):
		print(a_max[i][0] - a_max[i - 1][0], end=' ')
	print(n - a_max[-2][0] - 1)
elif k == 2:
	print(a_max[0][0] + 1, n - a_max[0][0] - 1)
else:
	print(n)


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = []
for i in range(len(a)):
	b.append([a[i], i])
b.sort()
ind = [0]
su = 0
for i in range(len(b) - k, len(b)):
	su += b[i][0]
	ind.append(b[i][1] + 1)
ind.sort()
ans = []
for i in range(1, len(ind) - 1):
	ans.append(ind[i] - ind[i - 1])
ans.append(n - ind[-2])
print(su)
print(*ans)


(n, k) = [int(i) for i in input().split()]
spisok = [int(i) for i in input().split()]
spisok2 = []
for i in range(n):
	spisok2.append([spisok[i], i + 1])

def sord(i):
	return i[0]

def sord1(i):
	return i[1]
spisok2.sort(key=sord, reverse=True)
spisok2 = spisok2[0:k]
spisok2.append([0, 0])
spisok2.sort(key=sord1, reverse=False)
spisok2[k][1] = n
sum = 0
for i in spisok2:
	sum += i[0]
print(sum)
for i in range(1, k + 1):
	print(spisok2[i][1] - spisok2[i - 1][1], end=' ')


(n, k) = map(int, input().split())
x = list(map(int, input().split()))
a = x.copy()
a.sort()
b = a[-k:]
(prev_index, flag) = (0, 0)
print(sum(b))
for i in range(n):
	if x[i] in b and flag == 0:
		b[b.index(x[i])] = 0
		flag = 1
	elif x[i] in b and flag == 1:
		print(i - prev_index, end=' ')
		b[b.index(x[i])] = 0
		prev_index = i
	if i == n - 1 and x[i] not in b:
		print(n - prev_index)


(n, k) = list(map(int, input().split()))
problems = list(map(int, input().split()))
sorted_problems = sorted(problems, reverse=True)
k_max = {}
total_profit = 0
for i in range(k):
	total_profit += sorted_problems[i]
	if sorted_problems[i] in k_max:
		k_max[sorted_problems[i]] += 1
	else:
		k_max[sorted_problems[i]] = 1
days = []
count = 0
for i in range(n):
	count += 1
	if problems[i] in k_max:
		k_max[problems[i]] -= 1
		if k_max[problems[i]] == 0:
			k_max.pop(problems[i], None)
		k -= 1
		if k > 0:
			days.append(str(count))
			count = 0
days.append(str(count))
print(total_profit)
print(' '.join(days))


(n, k) = map(int, input().split())
s = [int(x) for x in input().split()]
S = sorted(s)
S = S[::-1]
L = S[:k]
G = [0] * 2005
ans = 0
for j in range(0, len(L)):
	G[L[j]] = G[L[j]] + 1
	ans = ans + L[j]
d = []
R = []
for j in range(0, len(s)):
	if G[s[j]] > 0:
		G[s[j]] = G[s[j]] - 1
		d.append(s[j])
		R.append(d)
		d = []
	else:
		d.append(s[j])
if len(d) > 0:
	R[-1] = R[-1] + d
	d = []
print(ans)
for j in range(0, len(R)):
	R[j] = len(R[j])
for j in range(0, len(R)):
	print(R[j], end=' ')
print(' ')


maxnos = []
res = []
sum = 0
indexres = []
ddcopy = []
(n, k) = input().split()
n = int(n)
k = int(k)
difficulties = list(map(int, input().split()))
dcopy = difficulties.copy()
ddcopy = difficulties.copy()
for i in range(k):
	maxnos.append(max(dcopy))
	dcopy.remove(max(dcopy))
for i in range(k):
	res.append([])
index = 0
for j in maxnos:
	sum = sum + j
for x in difficulties:
	if index < k - 1:
		res[index].append(x)
		if x in maxnos:
			index = index + 1
			maxnos.remove(x)
		ddcopy.remove(x)
for x in ddcopy:
	res[k - 1].append(x)
for i in res:
	indexres.append(str(len(i)))
print(sum)
print(' '.join(indexres))


(n, k) = list(map(int, input().strip().split()))
nums = list(map(int, input().strip().split()))
sorted_nums = sorted(nums)
needed = {}
summ = 0
for i in range(n - 1, n - 1 - k, -1):
	cur = sorted_nums[i]
	summ += cur
	needed[cur] = needed.get(cur, 0) + 1
print(summ)
loc = []
for i in range(n):
	cur = nums[i]
	if needed.get(cur, 0) != 0:
		loc.append(i)
		needed[cur] -= 1
res = []
left = 0
for i in range(len(loc) - 1):
	res.append(str(loc[i] - left + 1))
	left = loc[i] + 1
res.append(str(n - left))
print(' '.join(res))


from heapq import nlargest
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
largest = nlargest(k, a)
print(sum(largest))
sizes = []
size = 0
for i in a:
	if i in largest:
		largest.remove(i)
		sizes.append(size + 1)
		size = 0
	else:
		size += 1
sizes[-1] += size
print(' '.join(map(str, sizes)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted([(a[i], i) for i in range(len(a))])[-k:]
b = sorted([i for (_, i) in b])
s = sum([a[i] for i in b])
print(s)
b = [-1] + b
b[-1] = max(b[-1], len(a) - 1)
print(' '.join([str(b[i] - b[i - 1]) for i in range(1, len(b))]))


import math
import itertools
getInputList = lambda : list(input().split())
getInputIntList = lambda : list(map(int, input().split()))
(n, k) = getInputIntList()
arr = getInputIntList()
newarr = []
for i in range(n):
	newarr.append([arr[i], i])
newarr.sort()
newarr = newarr[-k:]
s = 0
for i in newarr:
	s += i[0]
newarr = sorted(newarr, key=lambda x: x[1])
ans = []
if k > 1:
	ans.append(newarr[0][1] + 1)
	last = newarr[0][1]
	for i in newarr[1:len(newarr) - 1]:
		ans.append(i[1] - last)
		last = i[1]
	ans.append(n - (newarr[len(newarr) - 2][1] + 1))
else:
	ans.append(n)
print(s)
for i in ans:
	print(i, end=' ')


DEBUG = False

def dprint(*args, **kwargs):
	if DEBUG:
		print('\x1b[1;33;48m', end='')
		print('#>', *args, **kwargs)
		print('\x1b[0m', end='')
if not DEBUG:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
else:
	import random, time
	max_value = 2000
	(n, k) = (2000, 1000)
	random.seed(10)
	a = []
	for i in range(n):
		a.append(random.randint(1, max_value))
	t0 = time.clock()
x = []
for i in range(k):
	x.append((i, a[i]))
x.sort(key=lambda tup: tup[1], reverse=False)
for i in range(k, n):
	if a[i] > x[0][1]:
		del x[0]
		x.append((i, a[i]))
		x.sort(key=lambda tup: tup[1], reverse=False)
prev = -1
problems_sum = 0
tt = []
x.sort(key=lambda tup: tup[0], reverse=False)
for k in x:
	tt.append(k[0] - prev)
	prev = k[0]
	problems_sum += k[1]
print()
tt[-1] += n - sum(tt)
print(problems_sum)
for t in tt:
	print(t, end=' ')
print()
if DEBUG:
	t1 = time.clock()
	dprint('time:', t1 - t0)


(n, k) = map(int, input().split())
difficulties = list(map(int, input().split()))
indices = sorted(sorted(range(n), key=lambda i: difficulties[i], reverse=True)[:k])
total_profit = sum((difficulties[index] for index in indices))
numbers = [indices[0] + 1]
previous = indices[0]
for index in indices[1:]:
	numbers.append(index - previous)
	previous = index
numbers[-1] += n - 1 - previous
print(total_profit)
print(*numbers)


(n, k) = [int(i) for i in input().split()]
a = list(map(int, input().split()))
t = sorted(list(zip(a, range(n))), reverse=True)[:k]
print(sum(map(lambda x: x[0], t)))
t = sorted((i[1] for i in t))
t[-1] = n - 1
print(*(y - x for (x, y) in zip([-1] + t, t)))


(values_count, days) = [int(x) for x in input().split()]
values = [[int(x), i, False] for (i, x) in enumerate(input().split())]
values = sorted(values, key=lambda x: x[0])
general_utility = sum((x[0] for x in values[-days:]))
for i in range(days):
	k = i + 1
	values[-k][2] = True
values = sorted(values, key=lambda x: x[1])
result = []
count = 0
for (_, _, is_max) in values:
	count += 1
	if is_max:
		result.append(count)
		count = 0
else:
	if count != 0:
		result[-1] += count
print(general_utility)
print(' '.join((str(x) for x in result)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [(a[i], i) for i in range(n)]
b.sort(reverse=True)
if n == 1:
	print(a[0])
	print(1)
	exit()
if k == 1:
	print(max(a))
	print(n)
	exit()
ans = 0
for i in range(k):
	ans += b[i][0]
b = b[:k]
b.sort(key=lambda x: x[1])
b = [i[1] for i in b]
l = []
print(ans)
l.append(b[1])
for i in range(2, k):
	l.append(b[i] - b[i - 1])
l.append(n - b[-1])
print(*l)


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = []
for i in range(n):
	b.append((a[i], i))
b.sort(reverse=True)
c = []
sum = 0
for i in range(k):
	c.append(b[i][1])
	sum += b[i][0]
print(sum)
c.sort()
res = ''
prev = 0
for i in range(1, k):
	res += str(c[i] - prev) + ' '
	prev = c[i]
res += str(n - prev)
print(res)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(range(n))
b.sort(key=lambda e: a[e], reverse=True)
b = b[:k]
b.sort()
x = 0
for i in b:
	x += a[i]
b[-1] = n - 1
t = -1
print(x)
for i in b:
	print(i - t, end=' ')
	t = i


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = sorted(a, reverse=True)[:k]
prev = 0
print(sum(b))
for (ind, i) in enumerate(a):
	if len(b) == 1:
		print(n - ind, end=' ')
		break
	if i in b:
		print(ind + 1 - prev, end=' ')
		prev = ind + 1
		b.remove(i)


(n, k) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
if k == 1:
	print(max(a))
	print(n)
	exit(0)
ad = {}
for i in range(n):
	ad[i] = a[i]
index = sorted(ad.keys(), key=lambda x: ad[x], reverse=True)
topk = sorted(index[:k])
s = a[topk[0]]
t = [0] * k
t[0] = topk[0] + 1
for i in range(1, k - 1):
	t[i] = topk[i] - topk[i - 1]
	s += a[topk[i]]
t[k - 1] = n - sum(t)
s += a[topk[k - 1]]
print(s)
print(' '.join(map(str, t)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [(a[i], i) for i in range(n)]
b.sort(reverse=True)
index = []
for i in range(k):
	index.append(b[i][1])
index.sort()
index.pop()
index.append(n - 1)
ans = 0
for i in range(k):
	ans += b[i][0]
print(ans)
pre = -1
ans = []
for x in index:
	ans.append(x - pre)
	pre = x
print(*ans)


from sys import stdin, stdout
from collections import defaultdict
import math
import copy
(N, K) = [int(x) for x in stdin.readline().split()]
arr = [int(x) for x in stdin.readline().split()]
tmp = sorted(arr, reverse=True)[:K]
total = sum(tmp)
mark = [0] * N
for i in range(N):
	if arr[i] in tmp:
		tmp.remove(arr[i])
		mark[i] = 1
print(total)
if K == 1:
	print(N)
	quit()
idx = []
for i in range(N):
	if mark[i] == 1:
		idx.append(i)
idx.append(N)
for i in range(len(idx) - 1):
	if i == 0:
		print(idx[1], end=' ')
	else:
		print(idx[i + 1] - idx[i], end=' ')


(n, k) = map(int, input().split())
li = list(zip(map(int, input().split()), range(1, n + 1)))
li.sort(reverse=True)
cand = li[:k]
cand.sort(key=lambda x: x[1])
cand = [(0, 0)] + cand
su = 0
sol = []
for i in range(1, len(cand)):
	su += cand[i][0]
	sol.append(cand[i][1] - cand[i - 1][1])
sol[-1] += n - cand[-1][1]
print(su)
print(*sol)


from heapq import nlargest
(n, m) = tuple(map(int, input().split()))
a = list(map(int, input().split()))
idcs = sorted(nlargest(m, range(len(a)), key=lambda x: a[x]))
total = sum(nlargest(m, a))
i = -1
ans = []
for x in idcs:
	ans.append(x - i)
	i = x
ans[-1] += n - i - 1
assert sum(ans) == n
print(total)
print(' '.join(map(str, ans)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
idx = list(range(n))
for i in range(n):
	for j in range(i + 1, n):
		if a[i] > a[j]:
			(a[i], a[j]) = (a[j], a[i])
			(idx[i], idx[j]) = (idx[j], idx[i])
ans = sum(a[-k:])
idx = sorted(idx[-k:])
idx[0] = 0
idx.append(n)
print(ans)
for i in range(1, len(idx)):
	print(idx[i] - idx[i - 1], end=' ')


def readints():
	return [int(val) for val in input().strip().split()]

def main():
	(n, k) = readints()
	a = sorted(sorted(zip(readints(), range(1, n + 1)), reverse=True)[:k], key=lambda p: p[1])
	points = [(0, 0)] + a[:-1] + [(0, n)]
	print(sum((p[0] for p in a)))
	for i in range(k):
		print(points[i + 1][1] - points[i][1], end=' ')
main()


import random

class DataItem(object):

	def __init__(self, key, data):
		self.key = key
		self.data = data

class MaxHeap(object):

	def __init__(self):
		self.data = []
		self.length = 0
		self.heap_size = 0

	def build_heap(self, input_data):
		self.length = self.heap_size = len(input_data)
		self.data = input_data
		for idx in range(self.length // 2 - 1, -1, -1):
			self.heapify(idx)

	def heapify(self, idx):
		if idx >= self.heap_size:
			return
		l = (idx << 1) + 1
		r = (idx << 1) + 2
		if l >= self.heap_size:
			return
		largest = idx
		if self.data[l].key > self.data[idx].key:
			largest = l
		if r < self.heap_size and self.data[largest].key < self.data[r].key:
			largest = r
		if largest != idx:
			temp = self.data[idx]
			self.data[idx] = self.data[largest]
			self.data[largest] = temp
			self.heapify(largest)

	def extract_max(self):
		if self.heap_size < 1:
			return
		temp = self.data[0]
		self.data[0] = self.data[self.heap_size - 1]
		self.heap_size -= 1
		self.heapify(0)
		return temp

	def insert(self, item):
		if item is None:
			return
		if self.heap_size == 0:
			if self.length > 0:
				self.data[0] = item
			else:
				self.data = [item]
				self.length += 1
			self.heap_size += 1
			return
		if self.length == self.heap_size:
			self.data.append(self.data[0])
			self.length += 1
		else:
			self.data[self.heap_size] = self.data[0]
		self.data[0] = item
		self.heap_size += 1
		self.heapify(0)

def _partition(arr, low, high, pivot):
	temp = arr[high]
	arr[high] = arr[pivot]
	arr[pivot] = temp
	count = low
	pivot_key = arr[high].key
	for i in range(low, high + 1):
		if arr[i].key <= pivot_key:
			temp = arr[count]
			arr[count] = arr[i]
			arr[i] = temp
			count += 1
	return count - 1

def quick_sort(arr, low, high):
	if high - low + 1 <= 1:
		return
	pivot = random.choice(range(low, high + 1))
	idx = _partition(arr, low, high, pivot)
	quick_sort(arr, low, idx - 1)
	quick_sort(arr, idx + 1, high)
(n, k) = [int(x) for x in input().strip().split(' ')]
a = [DataItem(int(x), i) for (i, x) in enumerate(input().strip().split(' '))]
heap = MaxHeap()
heap.build_heap(a)
k_largest = [0] * k
total_profit = 0
for l in range(k):
	k_largest[l] = heap.extract_max()
	total_profit += k_largest[l].key
k_largest = [DataItem(x.data, x.key) for x in k_largest]
quick_sort(k_largest, 0, k - 1)
print(total_profit)
k_largest[-1].key = n - 1
print(k_largest[0].key + 1, end=' ')
for i in range(1, k):
	print(k_largest[i].key - k_largest[i - 1].key, end=' ')


(n, k) = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a1 = []
q = 0
for i in range(n):
	a1.append(a[i])
m = [0] * n
for i in range(k):
	m[a1.index(max(a1))] = max(a1)
	a1[a1.index(max(a1))] = 0
for i in range(len(m) - k):
	m.pop(m.index(0))
print(sum(m))
for i in range(n):
	q += 1
	if m != [] and m[0] == a[i]:
		m.pop(0)
		if m != []:
			print(q, end=' ')
			q = 0
print(q)


(n, k) = [int(e) for e in input().split(' ')]
L = [int(e) for e in input().split(' ')]
M = L[:]
M.sort()
M = M[-1:-k - 1:-1]
cursor = 0
print(sum(M))
for e in L:
	cursor += 1
	if e in M:
		M.remove(e)
		if M != []:
			print(cursor, end=' ')
			cursor = 0
		else:
			pass
print(cursor)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mxa = sorted(a)[-k:]
print(sum(mxa))
if k > 1:
	c = 0
	i = 0
	while c != k - 1:
		if a[i] in mxa:
			mxa.remove(a[i])
			print(len(a[:i + 1]), end=' ')
			a = a[i + 1:]
			c += 1
			i = 0
		else:
			i += 1
	print(len(a))
else:
	print(n)


(n, k) = map(int, input().split())
a = list(zip(map(int, input().split()), range(n)))
a.sort(reverse=True)
a = a[:k]
print(sum([x[0] for x in a]))
a.sort(key=lambda x: x[1])
start = 0
ans = []
for i in range(k - 1):
	ans.append(a[i][1] - start + 1)
	start = a[i][1] + 1
ans.append(n - start)
print(*ans)


[n, k] = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]
sorted_nums = list(nums)
sorted_nums.sort(reverse=1)
profit = 0
pts = []
for i in range(k):
	profit += sorted_nums[i]
	pts.append(sorted_nums[i])
indices = []
for i in range(n):
	if nums[i] in pts:
		indices.append(i)
		pts.remove(nums[i])
indices = indices[len(indices) - k + 1:]
print(profit)
if len(indices) > 0:
	print(indices[0], end=' ')
for i in range(1, len(indices)):
	print(indices[i] - indices[i - 1], end=' ')
if len(indices) > 0:
	print(n - indices[-1])
if len(indices) == 0:
	print(n)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
sorted_a = sorted(a)[::-1]
profits = []
for i in range(k):
	profits.append(sorted_a[i])
sum1 = sum(profits)
counts = []
if k == 1:
	print(sorted_a[0])
	print(n)
else:
	c = 0
	index = 1
	for i in range(n):
		if len(profits) == 0:
			break
		c += 1
		if a[i] in profits:
			if len(profits) == 1:
				c += n - i - 1
			profits.remove(a[i])
			index += 1
			counts.append(c)
			c = 0
	print(sum1)
	for i in counts:
		print(i, end=' ')


(n, k) = [int(i) for i in input().split(' ')]
l = [int(i) for i in input().split(' ')]
l1 = l.copy()
l1.sort(reverse=1)
m = l1[:k]
print(sum(m))
xx = 0
for i in range(n - 1):
	if l[i] in m:
		if len(m) == 1:
			break
		m.remove(l[i])
		print(i + 1 - xx, end=' ')
		xx = i + 1
print(n - xx)


import sys
(n, k) = [int(i) for i in sys.stdin.readline().split()]
a = [int(i) for i in sys.stdin.readline().split()]
assert n == len(a)
a_argmax = sorted(enumerate(a), key=lambda x: x[1], reverse=True)
k_peaks = a_argmax[:k]
indices = sorted([x[0] for x in k_peaks])
indices[-1] = len(a) - 1
score = 0
start = 0
days = []
for end_inclusive in indices:
	score += max(a[start:end_inclusive + 1])
	days += [end_inclusive + 1 - start]
	start = end_inclusive + 1
print(score)
print(' '.join((str(x) for x in days)))


(n, k) = map(int, input().split())
problems = list(map(int, input().split()))
indices = {}
for x in range(n):
	p = problems[x]
	if p not in indices:
		indices[p] = []
	indices[p].append(x)
problems = sorted(problems)[::-1]
days = []
profit = 0
for x in range(k):
	p = problems[x]
	days.append(indices[p][0])
	del indices[p][0]
	profit += problems[x]
days = sorted(days)
for x in range(1, k - 1):
	days[x] = days[x + 1] - days[x]
days[-1] = n - days[-1]
days[0] = n - sum(days[1:])
print(profit)
print(' '.join(map(str, days)))


from sys import stdin, stdout
import math
I = lambda : map(int, stdin.readline().split())
(n, k) = I()
a = list(I())
b = sorted(a, reverse=True)[0:k]
c = 1
ans = []
print(sum(b))
for x in a:
	if x in b:
		ans.append(c)
		b.remove(x)
		c = 1
	else:
		c += 1
	if len(b) == 0:
		break
ans[k - 1] = n - sum(ans) + ans[k - 1]
for x in ans:
	print(x, end=' ')
print('')


(N, K) = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A_p = [(p[1], p[0]) for p in enumerate(A)]
A_p.sort(reverse=True)
ans_sum = sum([p[0] for p in A_p[:K]])
top_k_pos = [p[1] + 1 for p in A_p[:K]]
top_k_pos.sort()
top_k_pos = top_k_pos[:-1]
top_k_pos.append(N)
top_k_pos.insert(0, 0)
print(ans_sum)
for i in range(1, len(top_k_pos)):
	prev = top_k_pos[i - 1]
	print(top_k_pos[i] - prev, end=' ')
print()


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr_i = []
for i in range(n):
	arr_i.append((i, arr[i]))
arr_i.sort(key=lambda r: r[1], reverse=True)
maxs_indexs = []
for i in arr_i[:k]:
	maxs_indexs.append(i[0])
maxs_indexs.sort()
sum = 0
for i in maxs_indexs:
	sum += arr[i]
print(sum)
bounds = []
for i in range(k - 1):
	bounds.append((maxs_indexs[i] + maxs_indexs[i + 1]) // 2 + (maxs_indexs[i] + maxs_indexs[i + 1]) % 2)
l = len(bounds)
if l == 0:
	print(n)
	exit(0)
print(bounds[0] - 0, end=' ')
for i in range(1, l):
	print(bounds[i] - bounds[i - 1], end=' ')
print(n - bounds[-1], end=' ')


from sys import stdin, stdout
(n, k) = [int(x) for x in stdin.readline().split()]
a = [int(x) for x in stdin.readline().split()]
b = [int(x) for x in a]
c = []
d = []
ans = []
b.sort()
b.reverse()
for i in range(k):
	c.append(b[i])
for i in range(len(c)):
	j2 = 0
	while True:
		j1 = a.index(c[i], j2, n) + 1
		if j1 not in d:
			d.append(j1)
			break
		else:
			j2 += 1
d.sort()
d[-1] = n
ans.append(d[0])
for i in range(1, len(d)):
	ans.append(d[i] - d[i - 1])
stdout.write(str(sum(c)) + '\n')
print(*ans)


(n, k) = map(int, input().split())
ara = list(map(int, input().strip().split()))
sorted_ara = sorted(ara)
sorted_ara.reverse()
ans = []
for i in range(k):
	ans.append(sorted_ara[i])
print(sum(ans))
segment = []
count = 0
for i in range(n):
	count += 1
	if ara[i] in ans:
		ans.remove(ara[i])
		segment.append(count)
		count = 0
total_element = sum(segment)
if total_element < n:
	segment[k - 1] += n - total_element
print(*segment, sep=' ')


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
indexes = sorted(sorted(range(len(a)), key=lambda x: a[x], reverse=True)[0:k])
maximum_total_profit = 0
part_index = 0
parts = [[] for _ in range(k)]
for (index, elem) in enumerate(a):
	if index in indexes and index != indexes[0]:
		part_index += 1
	parts[part_index].append(elem)
for index in indexes:
	maximum_total_profit += a[index]
print(maximum_total_profit)
for part in parts:
	print(len(part), end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append([a[i], i + 1])
b = sorted(b)[::-1]
id = [0]
s = 0
for i in range(k):
	id.append(b[i][1])
	s += b[i][0]
id = sorted(id)
print(s)
for i in range(1, len(id) - 1):
	print(id[i] - id[i - 1], end=' ')
print(n - id[-2])


(k, n) = map(int, input().split())
z = 0
p = 0
q = []
a = list(map(int, input().split()))
for i in range(n):
	m = a.index(max(a))
	p += a[m]
	q.append(m)
	a[m] = 0
q.sort()
print(p)
for i in range(n - 1):
	print(len(a[z:q[i] + 1]), end=' ')
	z = q[i] + 1
print(len(a[z:k]))


from collections import defaultdict
(n, k) = map(int, input().split())
maxi = 0
l = list(map(int, input().split()))
ans = []
z = l.copy()
z.sort(reverse=True)
yo = z[:k]
print(sum(z[:k]))
hash = defaultdict(int)
for i in yo:
	hash[i] += 1
ha = 0
last = -1
for (j, i) in enumerate(l):
	ha += 1
	if k == 0:
		break
	if i in yo and hash[i] != 0:
		last = j
		ans.append(ha)
		k -= 1
		ha = 0
		hash[i] -= 1
ans[-1] += n - last - 1
print(*ans)


(k, n) = list(map(int, input().split()))
a = list(map(int, input().split()))
o = 0
l = 0
for i in range(n):
	z = max(a)
	a[a.index(z)] = -1
	o = o + z
	l = l + 1
print(o)
j = 0
p = 0
for i in range(l - 1):
	while a[j] != -1:
		j = j + 1
	print(j + 1 - p, end=' ')
	p = j + 1
	j = j + 1
print(k - j)


(tasks, days) = map(int, input().split(' '))
diffs = list(map(int, input().split(' ')))

def maxExclusive(arr, exclusions):
	currMax = 0
	maxIdx = -1
	for i in range(len(arr)):
		if not i in exclusions and arr[i] > currMax:
			currMax = arr[i]
			maxIdx = i
	return maxIdx
maxs = []
while len(maxs) < days:
	maxs.append(maxExclusive(diffs, maxs))
maxs.sort()
print(sum(map(lambda x: diffs[x], maxs)))
perDay = []
for i in range(len(maxs)):
	if i == len(maxs) - 1:
		prev = maxs[i - 1] + 1 if i > 0 else 0
		perDay.append(tasks - prev)
	elif i == 0:
		perDay.append(maxs[i] + 1)
	else:
		perDay.append(maxs[i] - maxs[i - 1])
print(' '.join(map(str, perDay)))


import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
(N, K) = MAP()
A = [(a, i) for (i, a) in enumerate(LIST())]
A.sort(reverse=1)
idxs = set()
sm = 0
for i in range(K):
	idxs.add(A[i][1])
	sm += A[i][0]
ans = []
cnt = 0
for i in range(N):
	if i in idxs:
		cnt += 1
		ans.append(cnt)
		cnt = 0
	else:
		cnt += 1
ans[-1] += cnt
print(sm)
print(*ans)


from collections import *

def input_int():
	return list(map(int, input().split()))
vis = defaultdict(int)
(n, k) = input_int()
arr = input_int()
cnt = []
for (i, v) in enumerate(arr):
	cnt.append((-v, i))
cnt.sort()
c = k
t = 0
for (v, i) in cnt:
	c -= 1
	t += -v
	vis[i] = 1
	if c == 0:
		break
print(t)
now = 1
s = 0
for (i, v) in enumerate(arr):
	if vis[i]:
		k -= 1
		if k == 0:
			print(len(arr) - s, end=' ')
			break
		print(now, end=' ')
		s += now
		now = 1
	else:
		now += 1


string1 = input().split(' ')
n = int(string1[0])
k = int(string1[1])
string = input().split(' ')
a = []
for i in range(n):
	a.append(int(string[i]))
a_sorted = sorted(a)
max_tasks = a_sorted[-k:]
max_index = []
for i in range(n):
	if a[i] in max_tasks and max_tasks[max_tasks.index(a[i])]:
		max_index.append([i, a[i]])
		max_tasks[max_tasks.index(a[i])] = -1
benefit = 0
tasks = []
if len(max_index) == 1:
	print(max_index[0][1])
	print(len(a))
else:
	tasks.append(max_index[0][0] + 1)
	benefit += max_index[0][1]
	for i in range(1, k - 1):
		benefit += max_index[i][1]
		tasks.append(max_index[i][0] - max_index[i - 1][0])
	tasks.append(len(a) - max_index[k - 2][0] - 1)
	benefit += max_index[k - 1][1]
	print(benefit)
	for elem in tasks:
		print(elem, end=' ')


from operator import itemgetter as ig
(n, k) = map(int, input().split())
D = [(i + 1, v) for (i, v) in enumerate(map(int, input().split()))]
Y = sorted(sorted(D, key=ig(1))[-k:])
print(sum(map(ig(1), Y)))
d = [n] if k == 1 else [Y[0][0]] + [y[0] - Y[i][0] for (i, y) in enumerate(Y[1:-1])] + [n - Y[-2][0]]
print(' '.join(map(str, d)))


from operator import itemgetter
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ar = zip(a, range(n))
profit = sorted(ar, key=itemgetter(0), reverse=True)[:k]
total = sum((i[0] for i in profit))
print(total)
partitions = sorted((i[1] for i in profit)) + [n]
partitions[0] = 0
for (i, j) in zip(partitions, partitions[1:]):
	print(j - i, end=' ')


R = lambda : map(int, input().split())
(n, k) = R()
a = list(R())
b = sorted(a)
b = b[n - k:]
ans = []
print(sum(b))
k = 0
for t in a:
	k += 1
	if t in b:
		del b[b.index(t)]
		ans.append(k)
		k = 0
if k:
	ans[-1] += k
print(*ans, sep=' ')


def arranjo(nProblemas, dificuldadesProblemas, maisDificeis, kDias):
	estudoDiario = [0] * kDias
	dia = 0
	for i in range(nProblemas):
		estudoDiario[dia] += 1
		if dificuldadesProblemas[i] in maisDificeis:
			maisDificeis.remove(dificuldadesProblemas[i])
			if len(maisDificeis) != 0:
				dia += 1
	return ' '.join(map(str, estudoDiario))
entrada = input().split()
entradaProblemas = input().split()
nProblemas = int(entrada[0])
kDias = int(entrada[1])
dificuldadesProblemas = list(map(int, entradaProblemas))
maisDificeis = dificuldadesProblemas.copy()
maisDificeis.sort(reverse=True)
maisDificeis = maisDificeis[0:kDias]
profit = sum(maisDificeis)
print(profit)
print(arranjo(nProblemas, dificuldadesProblemas, maisDificeis, kDias))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k >= 2:
	cell_max = []
	cell_index = [-1]
	for i in range(k):
		max1 = 0
		index_max1 = 0
		for j in range(n):
			if a[j] > max1:
				max1 = a[j]
				index_max1 = j
		a[index_max1] = 0
		cell_max.append(max1)
		cell_index.append(index_max1)
	print(sum(cell_max))
	cell_index = sorted(cell_index)
	ans = []
	for i in range(k - 1):
		ans.append(cell_index[i + 1] - cell_index[i])
	ans.append(n - cell_index[-2] - 1)
	print(' '.join(map(str, ans)))
else:
	print(max(a))
	print(n)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math

def fact(x):
	if x == 0:
		return 1
	else:
		return x * fact(x - 1)

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = 0
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = 1
			break
	return ans
for t in range(1):
	(n, k) = map(int, input().split())
	diffi = list(map(int, input().split()))
	if k == 1:
		print(max(diffi))
		print(n)
	else:
		values = []
		for i in range(n):
			values.append((diffi[i], i))
		values.sort()
		values = values[n - k:]
		values.sort(key=lambda x: x[1])
		indices = [-1, n - 1]
		ans = 0
		for (val, ind) in values:
			ans += val
			indices.insert(-1, ind)
		indices.pop(-2)
		print(ans)
		for i in range(1, len(indices)):
			print(indices[i] - indices[i - 1], end=' ')
		print('')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] = (a[i], i)
a = [x for x in reversed(sorted(a))]
b = []
s = 0
for i in range(k):
	b += [a[i][1]]
	s += a[i][0]
print(s)
b = sorted(b)
b[k - 1] = n - 1
p = -1
for x in b:
	print(x - p, end=' ')
	p = x


(n, k) = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
res = sorted(sorted(range(len(a)), key=lambda i: a[i])[-k:])
r1 = 0
r2 = []
tmp = -1
for i in res:
	r1 += a[i]
	r2.append(i - tmp)
	tmp = i
if k > 1:
	r2[-1] = n - 1 - res[-2]
if k == 1:
	r2 = [n]
print(r1)
print(*r2)


(n, k) = map(int, input().split())
n = int(n)
k = int(k)
li = input().split()
for i in range(len(li)):
	li[i] = int(li[i])
b = sorted(li)
b = b[-k:]
s = sum(b)
print(s)
ans = []
k = 0
for t in li:
	k += 1
	if t in b:
		del b[b.index(t)]
		ans.append(k)
		k = 0
if k:
	ans[-1] += k
print(*ans, sep=' ')


(n, k) = map(int, input().split())
s = [int(i) for i in input().split()]
tasks = [0] * n
for i in range(n):
	tasks[i] = [s[i], i]
tasks.sort()
maxim = tasks[n - k:]
counter = 0
answer = []
for i in range(n):
	for j in maxim:
		if j[0] == s[i] and j[1] == i:
			answer.append(counter + 1)
			counter = -1
			break
		elif s[i] < j[0]:
			break
	counter += 1
answer[-1] += n - sum(answer)
q = 0
for i in maxim:
	q += i[0]
print(q)
print(' '.join(map(str, answer)))


(n, k) = map(int, input().split())
inpl = input().split()
pdl = [(int(inpl[i]), i + 1) for i in range(n)]
pdl.sort(reverse=True, key=lambda x: x[0])
pdkl = pdl[:k]
t = 0
for i in pdkl:
	t += i[0]
print(t)
pdkl.sort(key=lambda x: x[1])
t = 0
for i in pdkl[:-1]:
	print(i[1] - t, end=' ')
	t = i[1]
print(n - t)


(n, k) = map(int, input().split())
u = list(map(int, input().split()))
a = u[:]
a.sort()
d = -1
ans = 0
s = []
for i in range(k):
	ans += a[d]
	s.append(a[d])
	d -= 1
print(ans)
m = 0
j = 0
for i in range(n):
	if u[i] in s:
		j += 1
		if j < k:
			print(i + 1 - m, end=' ')
		else:
			print(n - m)
		m = i + 1
		s[s.index(u[i])] = -1


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
B = []
for (i, a) in enumerate(A):
	B.append((a, i))
B.sort(reverse=True)
B = B[0:k]
idx = []
ans = 0
for (a, i) in B:
	idx.append(i)
	ans += a
idx.sort()
s = []
pre = -1
for j in range(len(idx)):
	i = idx[j]
	if j != len(idx) - 1:
		s.append(i - pre)
		pre = i
	else:
		s.append(n - 1 - pre)
print(ans)
print(*s)


(length, days_count) = map(int, input().split())
data = list(map(int, input().split()))
data = sorted(enumerate(data), key=lambda x: x[1])[-days_count:]
s = sum((x[1] for x in data))
print(s)
if days_count == 1:
	print(length)
	exit(0)
days = [x[0] for x in sorted(data, key=lambda x: x[0])]
out = ''
(first_idx, last_idx) = (days[0], days[-1])
out += str(first_idx + 1)
left_idx = first_idx
days = days[1:-1]
for el in days:
	out += ' %s' % (el - left_idx)
	left_idx = el
if first_idx != last_idx:
	out += ' ' + str(length - left_idx - 1)
print(out)


from functools import reduce
a = list(input().split(' '))
(n, k) = (int(a[0]), int(a[1]))
a = list(input().split(' '))
a = list((int(x) for x in a))
new_a = sorted(a, reverse=True)
res = reduce(lambda x, y: x + y, new_a[0:k])
m = list(new_a[0:k])
itog = list()
for i in range(n):
	for j in range(len(m)):
		if a[i] == m[j]:
			itog.append(i)
			del m[j:j + 1]
			break
itog = sorted(itog)
ans = list()
last = -1
for i in range(len(itog)):
	if i == len(itog) - 1 and len(ans) > 0:
		ans.append(n - 1 - itog[len(itog) - 2])
	else:
		ans.append(itog[i] - last)
	last = itog[i]
if len(ans) == 1:
	ans[0] = n
print(res)
for x in ans:
	print(x, end=' ')


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
(n, k) = ris()
a = ris()
b = sorted(([-x, i] for (i, x) in enum(a)))
b = sorted(b[:k], key=lambda x: x[1])
b[-1][1] = n - 1
ans = []
s = j0 = 0
for i in range(k):
	(x, j) = (b[i][0], b[i][1] + 1)
	s += -x
	ans.append(j - j0)
	j0 = j
print(s)
print(*ans)


a = input()
b = input()
a = a.split(' ')
n = int(a[0])
k = int(a[1])
s = b.split(' ')
a = b.split(' ')
c = b.split(' ')
for i in range(n):
	s[i] = int(s[i])
	a[i] = int(a[i])
	c[i] = int(c[i])
s.sort()
s.reverse()
s = s[:k]
an = 0
xl = []
for i in range(k):
	x = c.index(s[i])
	c[x] = 0
	xl.append(x)
xl.sort()
st = ''
sm = 0
for i in range(k):
	if i == k - 1:
		l = a[an:n]
	else:
		l = a[an:xl[i] + 1]
	sm += max(l)
	st += str(len(l)) + ' '
	an = xl[i] + 1
print(sm)
print(st)


(n, days) = list(map(int, input().split()))
diff = list(map(int, input().split()))
index = []
for i in range(n):
	index.append([diff[i], i])
index.sort(reverse=True)
temp = []
sum = 0
for i in range(days):
	sum += index[i][0]
	temp.append(index[i][1])
print(sum)
temp.sort()
temp[-1] = n - 1
j = -1
for i in temp:
	print(i - j, end=' ')
	j = i


(n, k) = map(int, input().split())
a = []
for (i, x) in enumerate(list(map(int, input().split()))):
	a.append([x, i])
a = sorted(a)[-k:]
print(sum(map(lambda x: x[0], a)))
b = sorted(list(map(lambda x: x[1], a)))
if k == 1:
	print(n)
else:
	print(b[1], *(y - x for (x, y) in zip(b[1:], b[2:] + [n])))


(n, k) = map(int, input().split())
a = [(-1, 0)] + sorted(sorted(enumerate(map(int, input().split())), key=lambda x: x[::-1])[-k:])
print(sum(map(lambda x: x[1], a)))
a[-1] = (n - 1, 0)
print(' '.join(map(str, (a[i][0] - a[i - 1][0] for i in range(1, len(a))))))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = a.copy()
b.sort()
c = {}
s = 0
for i in b[-k:]:
	c[i] = c.setdefault(i, 0) + 1
	s += i
print(s)
d = 0
for i in range(n):
	if c.get(a[i], 0) > 0:
		c[a[i]] -= 1
		if k > 1:
			print(i + 1 - d, end=' ')
		else:
			print(n - d)
			quit()
		d = i + 1
		k -= 1
if n - d > 0:
	print(n - d)


import sys
import bisect
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
arr = []
for i in l:
	arr.append(i)
arr.sort()
ans = 0
ks = []
for i in range(1, k + 1):
	ks.append(arr[-i])
	ans += arr[-i]
ks.sort()
vec = []
prev = 0
s = 0
for i in range(n):
	if ks.count(l[i]) > 0:
		vec.append(i - prev + 1)
		s += i - prev + 1
		prev = i + 1
		ks.remove(l[i])
s -= vec[-1]
del vec[-1]
vec.append(n - s)
print(ans)
for i in vec:
	print(i, end=' ')


def calc(n, k, a):
	b = list(enumerate(a))
	b.sort(key=lambda x: x[1], reverse=True)
	b = b[:k]
	b.sort()
	s = 0
	last = 0
	ln = list()
	for cut in b:
		(index, item) = cut
		s += item
		ln.append(index - last)
		last = index
	ln[0] += 1
	ln[-1] += len(a) - last - 1
	return (s, ln)

def get_ints():
	return [int(n) for n in input().split()]

def get_floats():
	return [float(n) for n in input().split()]
a = get_ints()
assert len(a) == 2
(n, k) = (a[0], a[1])
a = get_ints()
assert len(a) == n
(res, ln) = calc(n, k, a)
print(res)
print(' '.join([str(i) for i in ln]))


I = lambda : map(int, input().split())
(n, k) = I()
A = sorted(enumerate(I()), key=lambda x: x[1], reverse=True)[:k]
X = sorted([i for (i, _) in A] + [-1])
X[-1] = n - 1
print(sum((a for (_, a) in A)))
print(*(X[i + 1] - X[i] for i in range(k)))


def myfun(c):
	return c[0]

def myfuck(c):
	return c[1]
(n, k) = map(int, input().split())
array = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append([array[i], i])
arr.sort(key=myfun)
arr1 = []
summ = 0
for i in range(1, k + 1):
	arr1.append(arr[-i])
	summ += arr[-i][0]
arr1.sort(key=myfuck)
ans = []
ans.append(arr1[0][1] + 1)
for i in range(1, k - 1):
	ans.append(arr1[i][1] - arr1[i - 1][1])
if k != 1:
	ans.append(n - arr1[k - 2][1] - 1)
print(summ)
if k != 1:
	print(*ans)
else:
	print(n)


[n, k] = list(map(int, input().split()))
arr = list(map(int, input().split()))
a = []
for i in range(n):
	a.append([arr[i], i + 1])
a.sort(reverse=True)
b = []
ans = 0
for i in range(k):
	ans += a[i][0]
	b.append(a[i][1])
b.sort()
print(ans)
shuru = 0
sol = []
for i in range(len(b)):
	if i != len(b) - 1:
		sol.append(b[i] - shuru)
		shuru = b[i]
	else:
		sol.append(n - shuru)
print(*sol)


(n, k) = map(int, input().split())
fas = list(map(int, input().split()))
mas = fas.copy()
mas.sort()
mas.reverse()
print(sum(mas[:k]))
ras = mas[:k]
gas = []
for el in ras:
	l = fas.index(el)
	gas.append(l + 1)
	fas[l] = -1
gas.sort()
nas = [gas[0]]
for i in range(1, k):
	nas.append(gas[i] - gas[i - 1])
nas[k - 1] += n - gas[k - 1]
nas = map(str, nas)
print(' '.join(nas))


(n, k) = input().split()
n = int(n)
k = int(k)
l = [int(x) for x in input().split()]
l = [(l[i], i) for i in range(len(l))]
l.sort()
f = l[-k:]
ix = [e[1] for e in f]
ts = sum([e[0] for e in f])
ix.sort()
ix2 = [ix[0] + 1] + [ix[x] - ix[x - 1] for x in range(1, len(ix))]
ix2[-1] = ix2[-1] + n - sum(ix2)
print(ts)
ix2 = [str(t) for t in ix2]
print(' '.join(ix2))


from sys import exit
(n, k) = [int(x) for x in input().split()]
arr = input().split()
arr = [int(x) for x in arr]
arr = list(enumerate(arr))
arr_sorted = sorted(arr, key=lambda x: x[1], reverse=True)
if k == 1:
	print(arr_sorted[0][1])
	print(n)
	exit(0)
selected = [x[0] for x in arr_sorted[:k]]
selected = sorted(selected)
print(sum([x[1] for x in arr_sorted[:k]]))
ans = [selected[0] + 1]
cur = 1
while cur < k - 1:
	ans.append(selected[cur] - selected[cur - 1])
	cur += 1
ans.append(n - selected[k - 2] - 1)
for x in ans:
	print(x, end=' ')
print()


(n, k) = map(int, input().split())
a = []
i = 1
for x in input().split():
	a.append((int(x), i))
	i += 1
a.sort(reverse=True)
a = a[:k]
a = sorted(a, key=lambda x: x[1])
total = 0
ans = []
if k == 1:
	print(a[0][0])
	print(n)
else:
	ans.append(a[0][1])
	total += a[0][0]
	for i in range(1, k - 1):
		ans.append(a[i][1] - a[i - 1][1])
		total += a[i][0]
	ans.append(n - a[k - 2][1])
	total += a[k - 1][0]
	print(total)
	for x in ans:
		print(x, end=' ')


__author__ = 'Juan Barros'

def solve(n, k, a):
	sum = 0
	maximunsIndex = [-1]
	maximuns = []
	while sum != k:
		maximum = max(a)
		maximunsIndex.append(maximum)
		maximuns.append(a[maximum])
		a[maximum] = -1
		sum += 1
	maximunsIndex.sort()
	result = []
	for i in range(1, len(maximunsIndex)):
		aux = maximunsIndex[i] - maximunsIndex[i - 1]
		if aux >= 1:
			result.append(aux)
	result[k - 1] = result[k - 1] + (n - 1 - maximunsIndex[k])
	return (result, maximuns)

def max(a):
	max = -1
	for i in range(len(a)):
		if a[i] >= a[max]:
			max = i
	return max
(n, k) = [int(element) for element in input().split(' ')]
a = [int(element) for element in input().split(' ')]
bests = solve(n, k, a)
print(sum(bests[1]))
print(' '.join((str(x) for x in bests[0])))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
d = {}
ans1 = 0
if k == 1:
	print(max(a))
	print(len(a))
else:
	for i in range(k):
		if b[i] in d:
			d[b[i]] += 1
		else:
			d[b[i]] = 1
		ans1 += b[i]
	print(ans1)
	for i in range(n):
		if a[i] in d and d[a[i]] > 0:
			d[a[i]] = d[a[i]] - 1
			a[i] = -1
	indices = [i for (i, x) in enumerate(a) if x == -1]
	l = len(indices)
	for i in range(l):
		if i == 0:
			print(indices[i] + 1, end=' ')
		elif i == l - 1:
			print(n - indices[i - 1] - 1, end=' ')
		else:
			print(indices[i] - indices[i - 1], end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
positions = []

def find_max_pos():
	cur_max = 0
	cur_pos = 0
	for i in range(n):
		if a[i] > cur_max:
			cur_max = a[i]
			cur_pos = i
	return cur_pos
ans = 0
d = {}
for j in range(k):
	i = find_max_pos()
	ans += a[i]
	positions.append(i)
	d[i] = a[i]
	a[i] = 0
for (i, v) in d.items():
	a[i] = v
positions.sort()
print(ans)
if k == 1:
	print(n)
else:
	print(len(a[:positions[1]]), end=' ')
	for i in range(1, len(positions)):
		if i == len(positions) - 1:
			print(len(a[positions[i]:]), end=' ')
		else:
			print(len(a[positions[i]:positions[i + 1]]), end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = 0
c = a[:]
c.sort()
b = c[n - k:n]
for i in range(n - k, n):
	s += c[i]
print(s)
k = 1
c = []
for i in range(n):
	if a[i] in b:
		c.append(k)
		k = 1
		del b[b.index(a[i])]
	else:
		k += 1
c[-1] += k - 1
for x in c:
	print(x, end=' ')


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [i for i in a]
a.sort()
d = {}
count = 0
ans = []
ans_sum = 0
for i in range(n):
	if not b[i] in d:
		d[b[i]] = []
	d[b[i]].append(i)
for i in reversed(range(n)):
	ans_sum += a[i]
	ans.append(d[a[i]][0])
	d[a[i]] = d[a[i]][1:]
	count += 1
	if count == k:
		break
print(ans_sum)
ans.sort()
ans = [-1] + ans
l = len(ans)
for i in range(1, l - 1):
	print(ans[i] - ans[i - 1], end=' ')
print(n - ans[-2] - 1)


from collections import Counter
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
s = sum(b[:k])
print(s)
c = Counter(b[:k])
l = []
i = j = x = 0
while len(l) < k - 1 and i < len(a):
	if a[i] in c and c[a[i]] > 0:
		c[a[i]] -= 1
		j += 1
		l.append(i + 1 - x)
		x = i + 1
	i += 1
l.append(len(a) - x)
print(*l)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
q = []
for i in range(n):
	q.append(a[i])
q.sort()
q = q[-m:]
s = 0
for i in range(m):
	s += q[i]
print(s)
s = 1
w = []
f = 1
for i in range(n):
	if a[0] in q:
		w.append(s)
		f += s
		s = 0
		q.remove(a[0])
	a.remove(a[0])
	s += 1
w[-1] += n - f + 1
for i in range(m):
	print(w[i], end=' ')


(n, k) = input().split()
n = int(n)
k = int(k)
a = list(map(int, input().split()))
if n <= k:
	r = 0
	for i in range(n):
		r += a[i]
	print(r)
	for i in range(n):
		print(1, end=' ')
else:
	r = 0
	b = [0] * k
	s = [a[i] for i in range(k)]
	for i in range(k, n):
		s.append(a[i])
		s.remove(min(s))
	for p in range(k):
		r += s[p]
	print(r)
	t = 0
	j = 1
	i = 0
	while t < k:
		if s[t] == a[i]:
			if t == k - 1 and i < n - 1:
				print(j + n - i - 1)
				t += 1
			else:
				print(j, end=' ')
				j = 1
				t += 1
		else:
			j += 1
		i += 1


from collections import Counter, defaultdict, deque
read = lambda : list(map(int, input().split()))
getinfo = lambda grid: print(list(map(print, grid)))
p = lambda x: print(x, end=' ')
mod = 10 ** 9 + 7
inf = float('inf')

def solve():
	res = 0
	d = defaultdict(int)
	c = a[:]
	a.sort(reverse=True)
	v = []
	for i in range(k):
		res += a[i]
		d[a[i]] += 1
	print(res)
	lastIndex = -1
	for i in range(n):
		if c[i] in d:
			d[c[i]] -= 1
			if d[c[i]] == 0:
				del d[c[i]]
			if not d:
				print(n - 1 - lastIndex, end='')
			else:
				print(i - lastIndex, end=' ')
			lastIndex = i
while True:
	try:
		(n, k) = read()
		a = read()
		if k == 1:
			print(max(a))
			print(n)
		else:
			solve()
	except:
		break


(n, k) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
aa = [[0] * 2 for i in range(n)]
for i in range(n):
	aa[i][0] = a[i]
	aa[i][1] = i
aa = sorted(aa, reverse=True, key=lambda x: x[0])
b = [0] * n
sm = 0
for i in range(k):
	b[aa[i][1]] = 1
	sm += aa[i][0]
ln = 1
ot = ''
kc = 0
for i in range(n):
	if b[i] == 1 and kc < k - 1:
		ot += str(ln) + ' '
		ln = 1
		kc += 1
	else:
		ln += 1
ot += str(ln - 1)
print(sm)
print(ot)


from sys import stdin

def FindMax(a):
	max = 0
	max_index = 0
	for (k, i) in enumerate(a):
		if i[1] != 1 and i[0] > max:
			max = i[0]
			max_index = k
	a[max_index][1] = 1
t = []
counter = 0
sum = 0
(n, k) = [int(i) for i in stdin.readline().split()]
a = [[int(i), 0] for i in stdin.readline().split()]
for _ in range(k):
	FindMax(a)
for i in range(n):
	counter += 1
	if a[i][1] == 1 and k == 1:
		sum += a[i][0]
		k -= 1
	elif a[i][1] == 1:
		t.append(counter)
		counter = 0
		sum += a[i][0]
		k -= 1
if counter > 0:
	t.append(counter)
print(sum)
print(*t)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
x = l[:]
x.sort(reverse=True)
z = x[:k]
print(sum(z))
c = 1
for i in range(n):
	if l[i] in z:
		k -= 1
		z.remove(l[i])
		if k == 0:
			print(c + n - i - 1, end=' ')
			exit(0)
		else:
			print(c, end=' ')
		c = 1
	else:
		c += 1


class CodeforcesTask1006BSolution:

	def __init__(self):
		self.result = ''
		self.n_k = []
		self.problems = []

	def read_input(self):
		self.n_k = [int(x) for x in input().split(' ')]
		self.problems = [int(x) for x in input().split(' ')]

	def process_task(self):
		to_solve = self.problems[:]
		to_solve.sort(reverse=True)
		to_solve = to_solve[:self.n_k[1]]
		max_points = sum(to_solve)
		days = []
		day = 0
		for x in range(self.n_k[0]):
			day += 1
			if self.problems[x] in to_solve:
				to_solve.remove(self.problems[x])
				days.append(day)
				day = 0
		days[-1] += day
		self.result = '{0}\n{1}'.format(max_points, ' '.join([str(x) for x in days]))

	def get_result(self):
		return self.result
Solution = CodeforcesTask1006BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


l1 = input()
(n, k) = l1.split()
k = int(k)
l2 = input()
js = [int(x) for x in l2.split()]
ss = js.copy()
ss.sort(reverse=True)
pl = ss[:k]
qq = []
sum = 0
for i in range(0, len(js)):
	if js[i] in pl:
		sum = sum + js[i]
		qq.insert(i, 1)
		pl.remove(js[i])
	else:
		qq.insert(i, 0)
con = 0
print(sum)
pp = []
for i in qq:
	con = con + 1
	if i == 1:
		pp.append(con)
		con = 0
pp[k - 1] = pp[k - 1] + con
for i in pp:
	print(i, end=' ')


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
ar = sorted(arr, reverse=True)
j = 1
d = 1
i = 0
l = ar[:k]
c = []
prev = 0
count = sum(ar[:k])
if k == 1:
	print(max(arr))
	print(n)
elif k == n:
	print(sum(arr))
	print('1 ' * n)
else:
	while i < n:
		if arr[i] not in l:
			i += 1
		else:
			d = i + 1
			c.append(d - prev)
			prev = d
			l[l.index(arr[i])] = 0
			i += 1
			k -= 1
		if k == 1:
			break
	sum1 = sum(c)
	c.append(n - sum1)
	print(count)
	print(' '.join((str(h) for h in c)))


(n, k) = map(int, input().strip().split(' '))
t = list(map(int, input().strip().split(' ')))
biggests = sorted(t, reverse=True)[:k]
print(sum(biggests))
jobs = 0
for i in range(len(t)):
	if k == 1:
		break
	jobs += 1
	for j in range(len(biggests)):
		if t[i] == biggests[j]:
			biggests[j] = 0
			print(jobs, end=' ')
			jobs = 0
			k -= 1
			break
print(n - i)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a = list(sorted(enumerate(a), reverse=True, key=lambda x: (x[1], x[0])))[:k]
a = list(sorted(a))
print(sum(map(lambda x: x[1], a)))
last = -1
for i in range(len(a) - 1):
	print(a[i][0] - last, end=' ')
	last = a[i][0]
print(n - last - 1)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = sorted(a)[-k:]
print(sum(b))
used = [0 for i in range(n)]
for elem in b:
	for i in range(n):
		if a[i] == elem and used[i] == 0:
			used[i] = 1
			break
last = 0
count = 0
ans = []
for i in range(n):
	if used[i]:
		ans.append(i - last + 1)
		last = i + 1
		count += 1
	if count == k:
		ans.pop()
		ans.append(n - sum(ans))
print(*ans)


(n, k) = map(int, input().split())
l1 = [int(x) for x in input().split()]
l2 = sorted(l1, reverse=True)[:k]
s = sum(l2)
r = []
last = -1
i = 0
while len(l2) > 0:
	if l1[i] in l2:
		r.append(i - last)
		last = i
		l2.remove(l1[i])
	i += 1
r[-1] += len(l1) - i
print(s)
print(*r)