#include <stdio.h>
#define N 100000
double cross2(double x1, double y1, double x2, double y2) {
return x1 * y2 - x2 * y1;
}
long long xx[N + 1], yy[N + 1];
double cross(int i, int j, int k) {
return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}
long long eval(int i, int x) {
return xx[i] * x + yy[i];
}
void solve(int *aa, long long *dp, int *kk, int n, long long c) {
static int qu[N + 1];
int i, head, cnt;
dp[0] = 0, xx[0] = aa[0], yy[0] = dp[0] - aa[0] * aa[0];
head = cnt = 0, qu[head + cnt++] = 0;
for (i = 1; i <= n; i++) {
while (cnt >= 2 && eval(qu[head], aa[i]) < eval(qu[head + 1], aa[i]))
head++, cnt--;
dp[i] = eval(qu[head], aa[i]) - c, kk[i] = kk[qu[head]] + 1;
xx[i] = aa[i], yy[i] = dp[i] - (long long) aa[i] * aa[i];
while (cnt >= 2 && cross(qu[head + cnt - 2], qu[head + cnt - 1], i) >= 0)
cnt--;
qu[head + cnt++] = i;
}
}
int main() {
static long long dp[N + 1], dq[N + 1];
static int aa[N + 1], kk[N + 1], ll[N + 1];
static char used[N];
int n, k, i, j;
long long lower, upper, x;
scanf("%d%d", &n, &k), k++;
for (i = 1; i <= n; i++) {
scanf("%d", &aa[i]);
aa[i] += aa[i - 1];
}
lower = -1, upper = 1000000000000000000;
while (upper - lower > 1) {
long long c = (lower + upper) / 2;
solve(aa, dp, kk, n, c);
if (kk[n] <= k)
upper = c;
else
lower = c;
}
solve(aa, dp, kk, n, upper);
solve(aa, dq, ll, n, upper - 1);
printf("%lld\n", dp[n] + upper * k);
for (i = n - 1, j = n, x = dp[j]; i >= 0; i--)
if (kk[i] <= k - 1 && k - 1 <= ll[i] && dp[i] + (long long) (aa[j] - aa[i]) * aa[i] - upper == x)
used[i] = 1, j = i, x = dp[j], k--;
for (i = 1; i < n; i++)
if (used[i])
printf("%d ", i);
printf("\n");
return 0;
}
