#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
vector<pair<long long,long long>>hull={};
vector<int>ind;
inline bool com(pair<long long,long long> a,pair<long long,long long> b)
{
if (a.first/a.second!=b.first/b.second)
return a.first/a.second < b.first/b.second;
a.first%=a.second;
b.first%=b.second;
return (a.first*b.second<b.first*a.second);
}
inline bool cw(pair<long long,long long> a,pair<long long,long long> b,pair<long long,long long> c)
{
return com({b.first-a.first,a.second-b.second},{c.first-b.first,b.second-c.second});
}
inline void insert(pair<long long,long long> x,int in)
{
while (hull.size()&&hull.back()==x)
{
hull.pop_back();
ind.pop_back();
}
while (hull.size()>1&&!cw(hull[hull.size()-2],hull.back(),x))
{
hull.pop_back();
ind.pop_back();
}
hull.push_back(x);
ind.push_back(in);
}
inline long long vl(pair<long long,long long> a,long long x)
{
return x*a.second+a.first;
}
pair<long long,int> query(long long x)
{
long long ans=vl(hull[0],x);
int in=ind[0];
int st=1,en=hull.size()-1;
while (st<=en)
{
int mid=(st+en)/2;
long long ans1=vl(hull[mid-1],x),ans2=vl(hull[mid],x);
if (ans1>ans2)
{
if (ans1>ans)
in=ind[mid-1];
ans=max(ans,ans1);
en=mid-1;
}
else
{
if (ans2>ans)
in=ind[mid];
ans=max(ans,ans2);
st=mid+1;
}
}
return {ans,in};
}
inline void solve()
{
int n,k;
cin>>n>>k;
int a[n+1]={};
long long p[n+1]={};
for (int i=1;i<=n;i++)
{
cin>>a[i];
p[i]=p[i-1]+a[i];
}
long long dp1[n+1]={};
for (int i=1;i<=n;i++)
dp1[i]=p[i]*(p[n]-p[i]);
long long dp[n+1]={};
int pre[k+1][n+1]={};
for (int l=2;l<=k;l++)
{
hull={};
ind={};
insert({dp1[l-1]-p[n]*p[l-1],p[l-1]},l-1);
for (int i=l;i<=n;i++)
{
pair<long long,long long> y=query(p[i]);
pre[l][i]=y.second;
dp[i]=y.first+(p[n]-p[i])*p[i];
insert({dp1[i]-p[n]*p[i],p[i]},i);
dp1[i]=dp[i];
dp[i]=0;
}
}
long long ans=-1;
int ind=1;
for (int i=1;i<=n;i++)
{
if (dp1[i]>ans)
{
ans=dp1[i];
ind=i;
}
}
int ans1[k]={};
for (int l=k;l>=1;l--)
{
ans1[l-1]=ind;
ind=pre[l][ind];
}
cout<<ans<<endl;
for (auto i:ans1)
cout<<i<<' ';
cout<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
