#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define MAX 101010
#define ln '\n'
lld arr[MAX], dp[MAX], p[MAX], s[MAX], ans[MAX];
int path[MAX][202];
void f(lld ind, lld l, lld r, lld low, lld high) {
if (l > r || low > high) return;
lld i, mid = (l + r) / 2, mini = mid - 1;
dp[mid] = 0;
for (i = max(low, ind - 1); i <= min(high, mid - 1); i++) {
if (dp[mid] < p[i] + s[i] * (s[mid] - s[i])) {
dp[mid] = p[i] + s[i] * (s[mid] - s[i]);
mini = i;
}
}
path[mid][ind] = (int)mini;
f(ind, l, mid - 1, low, mini);
f(ind, mid + 1, r, mini, high);
}
int main(void) {
ios::sync_with_stdio(0), cin.tie(0);
lld N, K;
cin >> N >> K;
lld i;
for (i = 1; i <= N; i++) {
cin >> arr[i];
s[i] = arr[i] + s[i - 1];
}
int j;
for (i = 2; i <= K + 1; i++) {
f(i, 1, N, 1, N);
for (j = 1; j <= N; j++) {
p[j] = dp[j];
}
}
cout << dp[N] << ln;
for (i = K + 1; i >= 2; i--) {
ans[i] = (lld)path[N][i];
N = (lld)path[N][i];
}
for (i = 2; i <= K + 1; i++) cout << ans[i] << ln;
return 0;
}
