#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define SZ(x) int(x.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxs(a, b) (a = max(a,b))
#define mins(a, b) (a = min(a,b))
#define Mp make_pair
#define mid ((l+r)>>1)
const int MXN = 1e5+1;
const int MXK = 201;
int n, k, a[MXN], S[MXN];
ll P[MXN];
inline ll cost(int l, int r) {
return P[r] - P[l-1] - ll(S[r]-S[l-1])*S[l-1];
}
ll dp[MXN], bef[MXN];
int par[MXN][MXK];
void divide(int x, int l=1, int r=n, int opl=1, int opr=n) {
if(l>r) return;
dp[mid] = 2e18;
par[mid][x] = 0;
for(int i=opl; i<=mid && i<=opr; i++) {
ll res = bef[i-1]+cost(i, mid);
if(res<=dp[mid]) {
dp[mid] = res;
par[mid][x]=i-1;
}
}
divide(x, l, mid-1, opl, par[mid][x]+1);
divide(x, mid+1, r, par[mid][x]+1, opr);
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) {
S[i] = S[i-1] + a[i];
P[i] = P[i-1] + (ll)S[i-1]*a[i];
}
for(int i=1; i<=n; i++) dp[i] = cost(1, i);
for(int i=1; i<=k; i++) {
for(int j=1; j<=n; j++) bef[j] = dp[j];
divide(i);
}
cout << P[n]-dp[n] << '\n';
for(int t=k, i=par[n][k]; t>=1; i=par[i][--t])
cout << i << ' ';
cout << '\n';
return 0;
}
