#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
int n, k;
ll a[maxn];
ll dp[2][maxn];
int tr[202][maxn];
void divide(int k, int l, int r, int st, int en) {
if (l > r) return;
int mid = (l + r) / 2;
int ret = -1;
for (int i = st; i <= en && i < mid; ++i)
if (i < mid && dp[1][mid] <= dp[0][i] + (a[mid] - a[i]) * a[i]) {
dp[1][mid] = dp[0][i] + (a[mid] - a[i]) * a[i];
tr[k][mid] = ret = i;
}
if (ret == -1)
return;
divide(k, l, mid - 1, st, ret);
divide(k, mid + 1, r, ret, en);
}
void trace(int k, int n) {
if (k == 0) return;
trace(k - 1, tr[k][n]);
cout << tr[k][n] << ' ';
}
int main(){
#define TASK "ABC"
// freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] += a[i - 1];
}
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= n; ++j) {
dp[0][j] = dp[1][j];
dp[1][j] = 0;
}
divide(i, i + 1, n, 1, n);
}
cout << dp[1][n] << '\n';
trace(k, n);
return 0;
}
