#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 = st;
for (int i = st; i <= en && i < mid; ++i)
if (i < mid && dp[k][mid] < dp[k - 1][i] + (a[mid] - a[i]) * a[i]) {
dp[k][mid] = dp[k - 1][i] + (a[mid] - a[i]) * a[i];
ret = i;
}
tr[k][mid] = ret;
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)
divide(i, i, n, 1, n);
cout << dp[k][n] << '\n';
trace(k, n);
return 0;
}
