#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
#define double long double
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
constexpr int N=1e5+100;
int n,k;
int a[N],s[N],f[N],g[N];
int dq[N],l,r;
int x(int i){
	return -s[i];
}
int y(int i){
	return g[i]-s[i]*s[i];
}
int dx(int i,int j){
	return x(i)-x(j);
}
int dy(int i,int j){
	return y(i)-y(j);
}
double ki(int i,int j){
	int x=dx(i,j),y=dy(i,j);
	if(dx==0)return -1e17;
	return 1.0*y/x;
}
int pre[N][300];
signed main(){
	R(n);R(k);
	for(int i=1;i<=n;i++)R(a[i]);
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	for(int t=1;t<=k;t++){
		for(int i=1;i<=n;i++)g[i]=f[i];
		l=1;r=0;
		dq[l]=1;
		for(int i=1;i<=n;i++){
			while(l<r&&ki(dq[l],dq[l+1])<=s[i])l++;
			f[i]=0;
			if(l<=r){
				int j=dq[l];
				f[i]=g[j]+s[j]*s[i]-s[j]*s[j];
				pre[i][t]=j;
			}
			while(l<r&&ki(dq[r],dq[r-1])>=ki(i,dq[r]))r--;
			dq[++r]=i;
		}
	}
	write(f[n]);push('\n');
	for(int x=pre[n][k];k;x=pre[x][--k])write(x),push(' ');
    return 0;
}