#include <bits/stdc++.h>
using namespace std;
#define min(...) minn(__VA_ARGS__)
#define max(...) maxx(__VA_ARGS__)
#define stringio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define m first
#define b second
char _;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename t>constexpr const t minn(const t x,const t y){return x<y?x:y;}
template<typename t,typename ...r>constexpr const t minn(const t x,const r ...xs){return minn(x,minn(xs...));}
template<typename t>constexpr const t maxx(const t x,const t y){return x>y?x:y;}
template<typename t,typename ...r>constexpr const t maxx(const t x,const r ...xs){return maxx(x,maxx(xs...));}
template <typename t> void scan (t& x) {do{while((x=getchar_unlocked())<'0'); for(x-='0'; '0'<=(_=getchar_unlocked()); x=(x<<3)+(x<<1)+_-'0');}while(0);}
template <typename t, typename ...r> void scan (t& x, r&... xs) {scan(x); scan(xs...);}
const int MAXN = 1e5+2, MAXK = 202;
ll dp[MAXN], psa[MAXN];
int par[MAXK][MAXN], which[MAXN];
pll lines[MAXN];
ll val (pll line, ll x) {return line.m * x + line.b;}
double intersect (pll f, pll s) {
ll i = f.b - s.b, j = s.m - f.m;
if (j < 0) j = -j, i = -i;
if (j == 0) return 1e18;
return (double)i/j;
}
int main() {
int n,K,l,r;
scan(n,K);
for (int i = 1; i <= n; i++) scan(psa[i]), psa[i] += psa[i-1];
lines[0] = {0,0}; which[0] = 0;
for (int k = 1; k <= K; k++) {
l = 0, r = 1;
for (int i = 1; i <= n; i++) {
while (r-l>1 && val(lines[l],psa[i]) <= val(lines[l+1],psa[i])) l++;
pll nline = {psa[i],dp[i] - psa[i] * psa[i]};
dp[i] = val(lines[l],psa[i]);
par[k][i] = which[l];
while (r-l>1 && intersect(nline,lines[r-1]) < intersect(lines[r-1],lines[r-2])) r--;
which[r] = i, lines[r++] = nline;
}
}
printf ("%lld\n",dp[n]);
int cur = n;
while (K) {
printf ("%d%c",par[K][cur]," \n"[K==1]);
cur = par[K--][cur];
}
return 0;
}
