#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define file(name) freopen(name".inp","r",stdin);freopen(name".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int inf=1e9+36;
const ll INF=4e18+36;
const long double EPS=1e-15;
const int N=2e5+5;
int minmize(int a,int b){
return a<b?a:b;
}
int maxmize(int a,int b){
return a>b?a:b;
}
ll Minmize(ll a,ll b){
return a<b?a:b;
}
ll Maxmize(ll a,ll b){
return a>b?a:b;
}
int n,k;
ll a[N],pre[N];
namespace soup3{
void solve(){
vector<vector<ll>>dp(k+2,vector<ll>(n+1,INF));
vector<vector<int>>trace(k+2,vector<int>(n+1,0));
vector<int>ans;
for(int i=1;i<=n;++i)
dp[1][i]=pre[i]*pre[i];
for(int l=2;l<=k+1;++l)
for(int i=l;i<=n;++i)
for(int j=l-1;j<i;++j){
ll val=dp[l-1][j]+(pre[i]-pre[j])*(pre[i]-pre[j]);
if(val<dp[l][i]){
dp[l][i]=val;
trace[l][i]=j;
}
}
cout<<(pre[n]*pre[n]-dp[k+1][n])/2LL<<'\n';
int cur=n;
for(int l=k+1;l>=1;--l){
if(trace[l][cur]>0)
ans.push_back(trace[l][cur]);
cur=trace[l][cur];
}
reverse(all(ans));
for(int i:ans)
cout<<i<<' ';
}
}
namespace cooked_soup{
struct Line{
ll a,b;
int id;
ll val(ll x){
return a*x+b;
}
};
vector<Line>convex;
int ptr;
bool bad(Line L1,Line L2,Line L3){
return (long double)(L3.b-L1.b)/(L1.a-L3.a)<(long double)(L2.b-L1.b)/(L1.a-L2.a);
}
void add_line(Line L){
convex.push_back(L);
while(convex.size()>=3&&bad(convex[convex.size()-3],convex[convex.size()-2],convex[convex.size()-1]))
convex.erase(convex.end()-2);
}
pair<ll,int>query(ll x){
while(ptr<(int)convex.size()-1&&convex[ptr+1].val(x)<=convex[ptr].val(x))
++ptr;
return {convex[ptr].val(x),convex[ptr].id};
}
void solve(){
vector<vector<ll>>dp(k+2,vector<ll>(n+1,INF));
vector<vector<int>>trace(k+2,vector<int>(n+1,0));
vector<int>ans;
for(int i=1;i<=n;++i)
dp[1][i]=pre[i]*pre[i];
for(int l=2;l<=k+1;++l){
ptr=0;
convex.clear();
add_line({-2*pre[l-1],dp[l-1][l-1]+pre[l-1]*pre[l-1],l-1});
for(int i=l;i<=n;++i){
auto[val,id]=query(pre[i]);
dp[l][i]=val+pre[i]*pre[i];
trace[l][i]=id;
if(i<n)
add_line({-2*pre[i],dp[l-1][i]+pre[i]*pre[i],i});
}
}
cout<<(pre[n]*pre[n]-dp[k+1][n])/2LL<<'\n';
int cur=n;
for(int l=k+1;l>=1;--l){
if(trace[l][cur]>0)
ans.push_back(trace[l][cur]);
cur=trace[l][cur];
}
reverse(all(ans));
for(int i:ans)
cout<<i<<' ';
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//file("Toi Yeu DHKA");
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
if(n<=1000)
soup3::solve();
else
cooked_soup::solve();
return 0;
}
