#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo n,k;
llo dp[100001];
llo dp2[100001];
llo pre[100001];
llo it[100001];
int back[202][100001];
llo cur=0;
void find(llo l,llo r,llo aa,llo bb){
llo mid=(l+r)/2;
pair<llo,llo> best={-1,-1};
for(llo i=aa;i<=min(bb,mid-1);i++){
// cout<<i<<"<"<<dp[i]<<","<<pre[mid]<<":"<<pre[i]<<endl;
llo cost=dp[i]+(pre[mid]-pre[i])*(pre[i]);
if(cost>best.a){
best={cost,i};
}
}
//cout<<mid<<","<<best.a<<","<<best.b<<","<<aa<<","<<bb<<endl;
dp2[mid]=best.a;
back[cur][mid]=best.b;
if(l<mid){
find(l,mid-1,aa,best.b);
}
if(mid<r){
find(mid+1,r,best.b,bb);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
for(llo i=0;i<n;i++){
cin>>it[i];
}
pre[0]=it[0];
for(llo i=1;i<n;i++){
pre[i]=pre[i-1]+it[i];
}
for(llo i=0;i<n;i++){
dp[i]=0;
}
for(llo i=1;i<k+1;i++){
cur+=1;
find(i,n-1,i-1,n-1);
for(llo j=0;j<n;j++){
dp[j]=dp2[j];
// cout<<dp[j]<<" ";
}
//cout<<endl;
}
cout<<dp[n-1]<<endl;
//vector<llo> ans;
int la=n;
for(llo i=k-1;i>=0;i--){
// ans.pb(back[i+1][ans.back()-1]+1);
la=back[i+1][la-1]+1;
cout<<la<<" ";
}
/*
for(llo j=k;j>0;j--){
cout<<ans[j]<<" ";
}*/
cout<<endl;
return 0;
}
