#include<bits/stdc++.h>
#define MAXN 100100
#define MAXK 202
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi first
#define se second
using namespace std;
class ConvexHull {
private:
static const int INF=(int)1e9+7;
struct Segment {
long long x,a,b;
int lineID;
Segment() {
x=a=b=0.0;
}
Segment(long long _x,long long _a,long long _b,int id) {
x=_x;a=_a;b=_b;lineID=id;
}
long long y(void) const {
return (a*x+b);
}
};
long long ceil(long long b,long long a) const {
assert(a>0);
long long x=b/a;
FOR(i,-2,2) if ((x+i)*a>b) return (x+i);
assert(false);
}
deque<Segment> dq;
long long lastA,lastB;
public:
ConvexHull() {
lastA=lastB=-INF;
};
void addLine(long long a,long long b,int id) {
//printf("ADD %lld %lld\n",a,b);
if (lastA>a || (lastA==a && lastB>=b)) return;
lastA=a;lastB=b;
while (!dq.empty() && dq.back().y()<=a*dq.back().x+b) dq.pop_back();
if (dq.empty()) {
dq.push_back(Segment(0,a,b,id));
return;
}
long long x=ceil(dq.back().b-b,a-dq.back().a);
dq.push_back(Segment(x,a,b,id));
while (!dq.empty() && dq.back().x>=INF) dq.pop_back();
}
pair<long long,int> query(int x) {
while (dq.size()>1 && dq[1].x<=x) dq.pop_front();
return (make_pair(dq.front().a*x+dq.front().b,dq.front().lineID));
}
};
int a[MAXN],s[MAXN],n,m;
long long dp[MAXN][MAXK];
int trc[MAXN][MAXK];
void init(void) {
scanf("%d%d",&n,&m);m++;
FOR(i,1,n) scanf("%d",&a[i]);
FOR(i,1,n) s[i]=s[i-1]+a[i];
}
void optimize(void) {
FOR(i,1,n) trc[i][1]=i;
FOR(j,2,m) {
ConvexHull ch;
FOR(i,j,n) {
ch.addLine(s[i-1],dp[i-1][j-1]-1LL*s[i-1]*s[i-1],i-1);
pair<long long,int> tmp=ch.query(s[i]);
dp[i][j]=tmp.fi;
trc[i][j]=tmp.se;
// printf("DP %d %d is %d\n",i,j,dp[i][j]);
}
}
}
void trace(void) {
cout<<dp[n][m]<<endl;
vector<int> val;
int i=n;
int j=m;
while (j>0) {
if (i<n) val.push_back(i);
i=trc[i][j];
j--;
}
sort(val.begin(),val.end());
REP(i,val.size()) printf("%d ",val[i]); printf("\n");
}
int main(void) {
#ifdef SKY
freopen("tmp.txt","r",stdin);
#endif // SKY
init();
optimize();
trace();
return 0;
}
