lines = list[tuple[int, int, int]]()
def inter(a, b):
return (lines[a][1] - lines[b][1]) / (lines[b][0] - lines[a][0])
def add(a, b, idx):
lines.append((a, b, idx))
while len(lines) > 2 and inter(-1, -2) < inter(-2, -3): lines.pop(-2)
def get(x):
s, e = 0, len(lines) - 1
while s < e:
m = s + e >> 1
if inter(m, m + 1) < x: s = m + 1
else: e = m
return e
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
for i in range(1, N + 1): A[i] += A[i - 1]
dp = [[0] * (N + 1) for _ in range(K + 1)]
# dp = [[[0, 0] for _ in range(N + 1)] for _ in range(K + 1)]
pre = [[0] * (N + 1) for _ in range(K + 1)]
for k in range(1, K + 1):
lines = []
add(A[1], dp[k - 1][0] - A[1] ** 2, 1)
for i in range(2, N + 1):
j = get(A[i])
dp[k][i] = A[i] * A[lines[j][2]] + dp[k - 1][lines[j][2]] - A[lines[j][2]] ** 2
pre[k][i] = lines[j][2]
if A[i] - A[i - 1] == 0: continue
add(A[i], dp[k - 1][i] - A[i] ** 2, i)
# for i in range(1, N + 1):
# dp[k][i] = max(dp[k - 1][j] + A[j] * (A[i] - A[j]) for j in range(i))
# dp[k][i] = max(A[i] * A[j] + dp[k - 1][j] - A[j] ** 2 for j in range(i))
# for j in range(i):
# if dp[k - 1][j] + A[j] * (A[i] - A[j]) > dp[k][i]:
# dp[k][i] = dp[k - 1][j] + A[j] * (A[i] - A[j])
# pre[k][i] = j
# if dp[k - 1][j][0] + A[j] * (A[i] - A[j]) > dp[k][i][0]:
# dp[k][i][0] = dp[k - 1][j][0] + A[j] * (A[i] - A[j])
# dp[k][i][1] = j
p = dp[K].index(max(dp[K]))
ans = []
for k in range(K, 0, -1):
p = pre[k][p]
ans.append(p)
print(max(dp[K]))
print(*ans[::-1])
