#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define pi 3.1415926535897932384626
using namespace std;
struct P{
int x,y,z;
bool operator <(const P &a)const
{
//if(x!=a.x)
return x<a.x;
// return z<a.z;
};
};
int dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
const ll mod=1000000007,Max=mod,Min=-Max;
int a,b;
int o[111111],c[222][111111];
ll dp[111111],ss[111111],aa[111111];
void f(int p,int n,int m,int x,int y)
{
if(n>m) return;
int h=(n+m)/2;
aa[h]=dp[h+1]+(ss[a]-ss[h])*o[h];
c[p][h]=h;
for(int i=max(x,h);i<=y;i++)
if(aa[h]<(ss[a]-ss[i])*(ss[i]-ss[h-1])+dp[i+1])
{
aa[h]=(ss[a]-ss[i])*(ss[i]-ss[h-1])+dp[i+1];
c[p][h]=i;
}
f(p,n,h-1,x,c[p][h]);
f(p,h+1,m,c[p][h],y);
}
int main()
{
scanf("%d %d",&a,&b);
for(int t=1;t<=a;t++)
{
scanf("%d",&o[t]);
ss[t]=ss[t-1]+o[t];
}
for(int t=1;t<=a;t++) c[0][t]=a;
for(int i=1;i<=b;i++)
{
aa[111111];
memset(aa,-1,sizeof(aa));
f(i,1,a,1,a);
for(int t=1;t<=a;t++)
dp[t]=aa[t];
}
printf("%lld\n",dp[1]);
int e=1;
for(int t=b;t;t--)
{
//printf("%d %d\n",c[t][e],e);
printf("%d ",c[t][e]);
e=c[t][e]+1;
}
}
