#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5, K = 205;
int n, k, a[N], q[N], pre[K][N];
ll sum[N], f[K][N];

inline ll X(int i) { return sum[i]; }
inline ll Y(int j, int i) { return f[j][i] - sum[i] * sum[i]; }
inline double slope(int j, int k1, int k2) {
    if (X(k2) == X(k1)) return Y(j, k2) > Y(j, k1) ? 1e18 : -1e18;
    return (double)(Y(j, k2) - Y(j, k1)) / (X(k2) - X(k1));
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }

    for (int j = 1; j <= k; j++) {
        int l = 0, r = 0;
        q[0] = 0;
        for (int i = 1; i <= n; i++) {
            while (l < r && slope(j - 1, q[l], q[l + 1]) >= -sum[i]) l++;
            int p = q[l];
            f[j][i] = f[j - 1][p] + sum[p] * (sum[i] - sum[p]);
            pre[j][i] = p;
            while (l < r && slope(j - 1, q[r - 1], q[r]) <= slope(j - 1, q[r], i)) r--;
            q[++r] = i;
        }
    }

    printf("%lld\n", f[k][n]);
    stack<int> st;
    for (int i = k, pos = n; i >= 1; i--) {
        pos = pre[i][pos];
        st.push(pos);
    }
    while (!st.empty()) {
        printf("%d ", st.top());
        st.pop();
    }
    return 0;
}