#include<bits/stdc++.h>
#define ll long long
#define MAXN 100007
using namespace std;
struct line
{
bool active=false;
ll k, n;
ll pos;
ll eval(ll x)
{
return k*x+n;
}
};
ll a[MAXN];
ll dp[203][MAXN]={};
ll back[203][MAXN]={};
ll pref[MAXN];
vector<line>st;
int pk;
double inter(line l1, line l2)
{
return (double)(l2.n-l1.n)/(l1.k-l2.k);
}
void addLine(line l)
{
while(st.size()>=2 && inter(st.back(),l)>=inter(st.back(),st[st.size()-2])) st.pop_back();
st.push_back(l);
}
pair<ll,int> getAns(ll x)
{
pk=min(pk,(int)st.size()-1);
while(pk<st.size()-1 && st[pk].eval(x)<st[pk+1].eval(x)) pk++;
return make_pair(st[pk].eval(x), st[pk].pos);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
pref[0]=0;
for(int i=1;i<=n;i++) pref[i]=a[i]+pref[i-1];
for(int i=1;i<=k;i++)
{
st.clear();
pk=0;
for(int j=2;j<=n;j++)
{
line l;
l.active=true;
l.pos=j-1;
l.n=dp[i-1][j-1]-pref[j-1]*pref[j-1];
l.k=pref[j-1];
addLine(l);
back[i][j]=getAns(pref[j]).second;
dp[i][j]=getAns(pref[j]).first;
}
}
cout<<dp[k][n]<<endl;
vector<int>t;
while(k>0)
{
t.push_back(back[k][n]);
n=back[k][n];
k--;
}
while(!t.empty())
{
cout<<t.back()<<" ";
t.pop_back();
}
}
