#include<bits/stdc++.h>
#define ll long long
#define all(v) begin(v), end(v)
#define pi pair<ll, ll>
#define vi vector<ll>
#define task "test"
using namespace std;
const ll maxn = 1e5+3;
ll n, k, a[maxn], tl=1, tr=0, dp[maxn][2], pf[maxn], sq[maxn];
int trace[maxn][205];
ll x, cnt[maxn];
vector<ll> ans;
ll cost(ll l, ll r){
return (pf[r] - pf[l-1])*pf[l-1];
}
void cmp(ll l, ll r, ll optl, ll optr, ll cur){
if(l > r) return ;
ll mid = (l+r)>>1, id = -1, mx = -1e18, v;
for(ll i = optl; i <= min(mid, optr); i++){
v = dp[i-1][0] + cost(i, mid);
if(v >= mx){
mx = v, id = i;
}
}
// cerr << l << " " << r << " " << mx << "\n";
dp[mid][1] = mx;
trace[mid][cur] = id;
if(l == r) return ;
cmp(l, mid-1, optl, id, cur);
cmp(mid+1, r, id, optr, cur);
}
int main(){
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
k++;
for(ll i = 1; i <= n; i++){
cin >> a[i];
pf[i] = pf[i-1] + a[i];
sq[i] = sq[i-1] + a[i]*a[i];
}
for(ll j = 2; j <= k; j++){
cmp(1, n, 1, n, j);
for(ll i = 1; i <= n; i++) dp[i][0] = dp[i][1];
// cout << "\n";
// for(ll i = 1; i <= n; i++) cout << dp[i][0] << " ";
}
cout << dp[n][0] << "\n";
// for(ll j = 1; j <= k; j++){
// for(ll i = 1; i <= n; i++) cout << trace[i][j] << " ";
// cout << "\n";
// }
ll pt = n;
for(ll i = k; i >= 2; i--){
ans.push_back(trace[pt][i]-1);
pt = trace[pt][i]-1;
}
reverse(all(ans));
for(auto x:ans) cout << x << " ";
return 0;
}
