#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
const int MXN = 1e5+2;
const int MXK = 202;
int n, k, a[MXN], S[MXN];
ll P[MXN];
void input() {
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
}
void init() {
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];
}
}
ll cost(int l, int r) {
return P[r] - P[l-1] - ll(S[r]-S[l-1])*S[l-1];
}
ll dp[MXN][MXK];
int par[MXN][MXK];
void divide(int x, int l=1, int r=n, int opl=1, int opr=n) {
if(l>r) return;
int mid = (l+r)>>1;
pll best = Mp(2e18, 0);
for(int i=opl; i<=mid && i<=opr; i++)
mins(best, pll(dp[i-1][x-1]+cost(i, mid), i));
dp[mid][x] = best.first;
par[mid][x] = best.second-1;
divide(x, l, mid-1, opl, best.second);
divide(x, mid+1, r, best.second, opr);
}
void base() {
for(int i=1; i<=n; i++) dp[i][0] = cost(1, i);
}
void solve() {
base();
for(int i=1; i<=k; i++) divide(i);
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
input();
init();
solve();
cout << P[n]-dp[n][k] << '\n';
for(int t=k, i=par[n][k]; t>=1; i=par[i][--t])
cout << i << ' ';
cout << '\n';
return 0;
}
