#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int MAXN=1e5,MAXK=201;
int opt[MAXK+1][MAXN+1];
int pre[MAXN+1];
vector<ll> DP,nxt;
const ll limit=1e18;
ll calc(int l,int r){
return (1LL*(pre[r]-pre[l-1])*(pre[r]-pre[l-1]));
}
void dnc(int phase,int l,int r,int optl,int optr){
if(l>r){
return;
}
int mid=((l+r)>>1);
for(int i=optl;i<=min(optr,mid-1);i++){
ll cost=calc(i+1,mid);
if(DP[i]+calc(i+1,mid)<nxt[mid]){
nxt[mid]=DP[i]+cost;
opt[phase][mid]=i;
}
}
dnc(phase,l,mid-1,optl,opt[phase][mid]);
dnc(phase,mid+1,r,opt[phase][mid],optr);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen("input.txt","r")){
freopen("input.txt","r",stdin);
}
if(fopen("sequence.in","r")){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
}
memset(opt,-1,sizeof(opt));
int n,k;
cin >> n >> k;
k++;
DP.assign(n+1,limit);
pre[0]=0;
for(int i=1;i<=n;i++){
int x;
cin >> x;
pre[i]=pre[i-1]+x;
}
DP[0]=0;
for(int i=1;i<=k;i++){
nxt.assign(n+1,limit);
dnc(i,i,n,0,n-1);
swap(DP,nxt);
}
ll ans=(calc(1,n)-DP[n])/2;
int pos=n;
cout << ans << endl;
for(int i=k;i>1;i--){
cout << opt[i][pos] << ' ';
pos=opt[i][pos];
}
}
