#include <iostream>
using namespace std;
using ll = long long;
const ll INF = 4e18;
const ll MAXN = 100008;
const ll MAXK = 208;
ll a[MAXN];
ll psm_[MAXN];
ll psqsm_[MAXN];
ll* psm = psm_ + 1;
ll* psqsm = psqsm_ + 1;
ll dp_[MAXK][MAXN];
ll* dp[MAXK];
ll opt_[MAXK][MAXN];
ll* opt[MAXK];
void get_layer(ll t, ll l, ll r, ll pl, ll pr) {
if (r - l <= 0)
return;
ll m = (l + r) / 2;
opt[t][m] = pl;
for (ll i = pl; i <= pr && i < m; ++i) {
ll sqsm = psqsm[m] - psqsm[i];
ll sm = psm[m] - psm[i];
if (dp[t][m] > dp[t - 1][i] + (sm * sm - sqsm) / 2) {
dp[t][m] = dp[t - 1][i] + (sm * sm - sqsm) / 2;
opt[t][m] = i;
}
}
get_layer(t, l, m, pl, opt[t][m]);
get_layer(t, m + 1, r, opt[t][m], pr);
}
signed main() {
ll n, k;
cin >> n >> k;
++k;
if (n >= MAXN || k >= MAXK)
return 0;
for (ll i = 0; i < n; ++i)
cin >> a[i];
for (ll i = 0; i < k; ++i) {
dp[i] = dp_[i] + 1;
opt[i] = opt_[i] + 1;
}
for (ll i = 0; i < n; ++i) {
psm[i] = psm[i - 1] + a[i];
psqsm[i] = psqsm[i - 1] + a[i] * a[i];
dp[0][i] = (psm[i] * psm[i] - psqsm[i]) / 2;
opt[0][i] = -1;
}
for (ll t = 1; t < k; ++t) {
for (ll i = 0; i < n; ++i) {
dp[t][i] = INF;
}
get_layer(t, t, n, t - 1, n - 1);
}
ll ans = 0;
for (ll i = 0; i < n; ++i)
ans += a[i];
ans *= ans;
for (ll i = 0; i < n; ++i)
ans -= a[i] * a[i];
ans /= 2;
ans -= dp[k - 1][n - 1];
cout << ans << endl;
ll i = n - 1;
ll t = k;
while (--t) {
i = opt[t][i];
if (i != -1) {
cout << i + 1 << ' ';
}
}
cout << endl;
}
